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 types
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.


  • -1
    minhduc2011  commented on Nov. 14, 2025, 2:58 p.m.

    include <bits/stdc++.h>

    define ll long long

    define pb push_back

    define pol LLONG_MAX

    define pel LLONG_MIN

    define ull unsigned long long

    define rep(i,a,b) for(int i=a;i<b;i++)

    define fope(name) if(fopen(name".inp","r")){freopen(name".inp","r",stdin);freopen(name".out","w",stdout);}

    using namespace std; const ll MOD = 1e9+7; const ll INF = 1000005; ll n,m,k,x=0,d1=0,z,ans,res; ll a[INF],f[INF]; void input(){ cin >> n; f[0]=0; for(ll i=1;i<=n;i++){ f[i]=f[i-1]; cin >> a[i]; f[i]+=a[i]; } } void output(){
    ans=0; for(ll k=1;k<=n;k++){ ll i=k,j=k+1; ll st=a[i],ss=a[j]; while(true){ if(st==ss) ans=max(ans,j-i+1); if(st>ss){ if(j<n){ j++; ss=ss+a[j]; } else break; } else{ if(i>1){ i--; st+=a[i]; } else break; } } } cout << ans; } int main(){ ios::syncwithstdio(0);
    cin.tie(0); fope("day2sum"); input(); output(); return 0;
    }


  • 1
    ngoccaidu2008  commented on Oct. 29, 2025, 2:33 p.m.

    Ý tưởng với mỗi giá trị k ta mở rộng từ trung tâm

    code tham khảo:

    #include <bits/stdc++.h>
using namespace std;
#define int long long
#define __Hormer_Nguyen__ signed main()
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
const int maxn=5+1e6;
int n;
int a[maxn];
int ans=0;
__Hormer_Nguyen__
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    for (int k=1;k<n;k++)
    {
        int i=k,j=k+1;
        int st=a[i],ss=a[j];
        while (true)
        {
            if (st==ss) ans=max(ans,j-i+1);
            if (st>ss)
            {
                if (j<=n-1)
                {
                    j++;
                    ss+=a[j];
                }else break;
            }else
            {
                if (i>=2)
                {
                    i--;
                    st+=a[i];
                }else break;
            }
        }
    }cout<<ans;
}

  • 2
    vominhmanh10  commented on Sept. 16, 2025, 12:27 p.m. ← edit 3

    với mỗi k, hai con trỏ đối xứng rộng ra là được, áp dụng với 2 * p[k] = p[l] + p[r] cho đoạn [l + 1...r], O(n^2) ok rồi, làm có 0,07s hà

    #include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    vector<int> a(n), p(n + 1, 0);
    for (int &x : a) cin >> x;
    for (int i = 1; i <= n; i++) p[i] = p[i - 1] + a[i - 1];
    int ans = 0;
    for (int k = 1; k < n; k++) {
        int l = k - 1, r = k + 1;
        while (l >= 0 && r <= n) {
            int x = p[l] + p[r];
            if (x == 2 * p[k]) {
                ans = max(ans, r - l);
                l--; r++;
            }
            else if (x > 2 * p[k]) l--;
            else r++;
        }
    }
    cout << ans;
}

  • 6
    huygd  commented on Aug. 30, 2024, 6:40 a.m.

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


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

    ai hd mik lam bai nay vs mik cam on


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

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


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


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

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


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

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


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

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


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

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


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

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


  • -12
    nguyenoanh93  commented on April 13, 2023, 1:33 a.m. ← edited

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


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

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


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

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


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

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


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

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