Sum of Vectors

View as PDF

Submit solution

Points: 0.90 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
COI 03
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Vector được biểu diễn bởi 1 cặp ~(X,Y)~. Tổng các vecto là tổng các thành phần tương ứng. e.g. ~(1,2)+(3,4)+(5,6) = (1+3+5,2+4+6) = (9,12)~. Khối lượng vecto ~(x~, ~y)~ là ~x \times x+y \times y~. Cho ~N~ vecto, tìm một tập con mà tổng của chúng có khối lượng lớn nhất. Kết quả là số ~64~ bit.

Input

  • Dòng đầu là ~N~, ~1 \leq N \leq 30\,000~, số vector.
  • ~N~ dòng tiếp theo là ~N~ vecto ~(X~, ~Y)~ (~-30\,000 \leq X~, ~Y \leq 30\,000~). Không có vector nào là ~(0~, ~0)~

Output

Ghi khối lượng lớn nhất tìm được

Sample Input 1

5 
5 -8 
-4 2 
4 -2 
2 1 
-6 4

Sample Output 1

202

Sample Input 2

4 
1 4 
-1 -1 
1 -1 
-1 4

Sample Output 2

64

Sample Input 3

9 
0 1 
6 8 
0 -1 
0 6 
-1 1 
-1 2 
5 -4 
1 0 
6 -5

Sample Output 3

360

Comments

Please read the guidelines before commenting.


There are no comments at the moment.