TWOSUM - Dãy 2-Sum
Giới hạn- Thời gian: 0.1s
- 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.
Một dãy các số nguyên không âm A[1..N] được gọi là 2-Sum nếu ta có thể tách dãy đó làm 2 dãy có tổng các giá trị bằng nhau. Nghĩa là tồn tại một số k trong đoạn [1..N-1] sao cho tổng A[1] + A[2] + ... + A[k] = A[k+1] + A[k+2] + ... + A[N].
Cho 1 dãy gồm N số nguyên không âm. Hãy tìm dãy con gồm các phần tử liên tiếp dài nhất mà cũng là dãy 2-Sum.
Input
Dòng đầu tiên chứa số nguyên N (2 <= N <= 5000).
N dòng tiếp theo, dòng thứ i chứa giá trị của phần tử A[i] của dãy. (0 <= A[i] <= 200000)
Output
Xuất ra độ dài lớn nhất của dãy 2-Sum tìm được. Nếu không có kết quả thì in ra 0.
Example
Input: 6
2
10
3
2
5
1
Output: 4
Giải thích: dãy 2-Sum dài nhất tìm được là A[2..5] = {10, 3, 2, 5}. Có thể tách dãy này thành 2 phần {10} và {3, 2, 5} có tổng bằng 10.
- Người up: yenthanh132