Sum of Vectors

Xem dạng PDF

Gửi bài giải


Điểm: 0,90 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
COI 03
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.