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++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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.



  • 0
    nguyenhuubaohv  commented on June 22, 2024, 6:19 p.m.

    ai hd mik lam bai nay vs mik cam on


  • -4
    nhatday1  commented on Oct. 13, 2023, 8:36 a.m.

    helo


  • 5
    Cadoc  commented on July 9, 2023, 3:14 p.m.

    mình code 2 pointer bth AC xong vào thấy các ngài code chặt nhị phân tự nhiên thấy hoang mang ghê @@


    • -8
      quyet  commented on Aug. 3, 2023, 8:54 a.m.

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


      • 0
        darwinkay2201  commented on July 21, 2024, 5:52 p.m.

        tui làm vẫn AC ngon


    • -7
      hmkhanh472010  commented on July 10, 2023, 1:47 a.m.

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


  • -10
    MaiThanh1342  commented on June 23, 2023, 3:00 p.m.

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


  • -9
    nguyenoanh93  commented on April 13, 2023, 2:53 a.m.

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


  • -7
    nguyenoanh93  commented on April 13, 2023, 1:33 a.m.

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


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

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


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

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


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

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


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

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