https://www.acmicpc.net/problem/2143


한 1시간 30분정도 고민했는데 모르겠음 ㅇㅅㅇ


#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()
{
    // 골드 3 문제 (정답률 30%)
    // 한 배열에 A[1], A[2],...에 대해 부 배열은 A[i], ... A[j] (1<=i<=j<=n)을 말함.
    // 부 배열의 합 = i~j번째까지 더한거.
    // A랑 B배열 주어졌을 때, A부+B부 = T가 되는 쌍의 개수를 구하라.

    // A, B 배열 총 길이 = 1000.

    // 입력받는 부분
    ll T;
    int n, m;
   
    cin >> T;
    int tmp;
    cin >> n;
    int *A, *B;
    A = new int[n];

    for(int i=0;i<n; i++)
    {
        cin >> A[i];
    }
    cin >> m;

    B = new int[m];
    for(int j=0; j<m; j++)
    {
        cin >> B[j];
    }

    // A, B의 부분합 DP 벡터
    vector<ll> DPA;
    vector<ll> DPB;

    // 부분합 저장
    for(int i=0; i<n; i++)
    {
        tmp=0;
        for(int j=i; j<n; j++)
        {
            tmp += A[j];
            DPA.push_back(tmp);
        }
    }
    for(int i=0; i<m; i++)
    {
        tmp = 0;
        for(int j=i; j<m; j++)
        {
            tmp += B[j];
            DPB.push_back(tmp);
        }
    }
    // 부분합 정렬
    sort(DPA.begin(), DPA.end());
    sort(DPB.begin(), DPB.end(), greater<ll>());

    // answer
    int cnt = 0;

    int szn = DPA.size();
    int szm = DPB.size();

    int idxa=0;
    int idxb=0;

    // for(auto p : DPA) cout << p << " ";
    // cout << "\n";
    // for(auto p : DPB) cout << p << " ";
    // cout << "\n";
   

    // 투포인터 형태로 정답값과 일치하는 조합 수 계산하기.
    while(idxa <szn && idxb < szm)
    {
        ll s = DPA[idxa] + DPB[idxb];
        // cout << idxa << " " << idxb << " " << s << "\n";
        if(s==T)
        {
            // cnt ++;
            int cn1 = 1;
            int cn2 = 1;
            int idxtmp = idxa;
            while(idxtmp < szn-1 && DPA[idxtmp] == DPA[idxtmp+1]) {cn1 ++; idxtmp++;}
            idxtmp = idxb;
            while(idxtmp < szm-1 && DPB[idxtmp] == DPB[idxtmp+1]) {cn2 ++; idxtmp++;}
            cnt += (cn1*cn2);
            idxa += cn1;
            idxb += cn2;
        }
        else if(s<T)
        {
            idxa ++;
        }
        else
        {
            idxb ++;
        }
    }

    std::cout << cnt;
}