MVECTOR - Sum of Vectors
Giới hạn- Thời gian: 0.213s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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*x+y*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 ≤ N ≤ 30,000, số vector. N dòng tiếp theo là N vecto (X,Y) -30,000 ≤ X,Y ≤ 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
suma.in
5
5 -8
-4 2
4 -2
2 1
-6 4
suma.out
202
suma.in
4
1 4
-1 -1
1 -1
-1 4
suma.out
64
suma.in
9
0 1
6 8
0 -1
0 6
-1 1
-1 2
5 -4
1 0
6 -5
suma.out
360
- Người up: vdmedragon
- Nguồn bài: COI 03