Processing math: 100%

Prijavi problem


Obeleži sve kategorije koje odgovaraju problemu

Još detalja - opišite nam problem


Uspešno ste prijavili problem!
Status problema i sve dodatne informacije možete pratiti klikom na link.
Nažalost nismo trenutno u mogućnosti da obradimo vaš zahtev.
Molimo vas da pokušate kasnije.
Pitanja na Algori

BBC7HVectors

vreme memorija ulaz izlaz
0,5 s 16 Mb standardni izlaz standardni ulaz

A set of m vectors {v1,v2, ...,vm} in Rd (the set of d-tuples of real numbers) is said to be linearly independent if the only reals λ12,...,λm that satisfy λ1 v1 + λ2 v2 + ... + λm vm = 0 are λ1 = λ2 = ... = λm = 0. For example, in R2 the set of vectors {(1 0), (0 1)} is linearly independent. However, {(1 0), (0 1), (1 1)} is not since 1 ∙ (1 0) + 1 ∙ (0 1) + (-1) ∙ (1 1) = (0 0).

In this task, you are given n vectors in Rd, and every vector has some weight. Your job is to find a linearly independent set of vectors with maximal sum of weights.

The first line contains two integers d and n. The next n lines contain d+1 integers each, separated with one empty space between any two integers. The first d numbers in the line i+1 are coordinates of the ith vector, and the last number is its weight.

The output should consist a single integer: the sum of weights of vectors in your set.

 

  • 1 ≤ d ≤ 200
  • 1 ≤ n ≤ 500
  • The coordinates of the vectors are integers in the range [-103,103].
  • The weights of the vectors are integers in the range [-106,106].

Ulaz izlaz

4 4
1 0 0 0 30
0 0 1 0 30
1 0 1 0 100
0 0 0 1 1

131

Morate biti ulogovani kako biste poslali zadatak na evaluaciju.