Dãy 2-Sum

Xem dạng PDF

Gửi bài giải


Điểm: 0,89 (OI)
Giới hạn thời gian: 0.38s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
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.


Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 3
    huygd  đã bình luận lúc 30, Tháng 8, 2024, 6:40

    Bài này prefix sum vẫn ac được!


  • -4
    nguyenhuubaohv  đã bình luận lúc 22, Tháng 6, 2024, 18:19

    ai hd mik lam bai nay vs mik cam on


  • -7
    nhatday1  đã bình luận lúc 13, Tháng 10, 2023, 8:36

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 4
    Cadoc  đã bình luận lúc 9, Tháng 7, 2023, 15:14

    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ê @@


    • -11
      quyet  đã bình luận lúc 3, Tháng 8, 2023, 8:54

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


      • -3
        darwinkay2201  đã bình luận lúc 21, Tháng 7, 2024, 17:52

        tui làm vẫn AC ngon


    • -12
      hmkhanh472010  đã bình luận lúc 10, Tháng 7, 2023, 1:47

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -14
    MaiThanh1342  đã bình luận lúc 23, Tháng 6, 2023, 15:00

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -12
    nguyenoanh93  đã bình luận lúc 13, Tháng 4, 2023, 2:53

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -10
    nguyenoanh93  đã bình luận lúc 13, Tháng 4, 2023, 1:33 chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -21
    abcn2211  đã bình luận lúc 3, Tháng 9, 2022, 12:32

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -37
    shiinehata  đã bình luận lúc 17, Tháng 12, 2021, 17:21

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -14
      dangbesttoan24  đã bình luận lúc 20, Tháng 10, 2022, 16:46

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -86
    DoanTungLamKoCopyCode  đã bình luận lúc 2, Tháng 11, 2021, 9:10

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.