Dãy 2-Sum

View as PDF

Submit solution

Points: 0.89 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Một dãy các số nguyên không âm ~A_{1 \dots 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 \dots N-1]~ sao cho tổng ~A_{1} + A_{2} + \dots + A_{k} = A_{k + 1} + A_{k + 2} + \dots + 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 \le N \le 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 \le A_{i} \le 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~.

Sample Input

6
2
10
3
2
5
1

Sample Output

4

Note

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.


Comments

Please read the guidelines before commenting.



  • -10
    abcn2211  commented on Sept. 3, 2022, 12:32 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -20
    shiinehata  commented on Dec. 17, 2021, 5:21 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -3
      dangbesttoan24  commented on Oct. 20, 2022, 4:46 p.m.

      sao mình làm như bạn thì TLE nhỉ :v


  • -37
    DoanTungLamKoCopyCode  commented on Nov. 2, 2021, 9:10 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.