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:
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