백준 2143번 두배열의 합(C++,누적합)⭐⭐

옛날에 푼건데.. 

투포인터 -> 정렬 후 끝에서 내려와야 반복 안함

메모리 초과조심 

#include <iostream>
#include <vector>
#include <algorithm>
#include<queue>
#include<map>
#include<unordered_map>
#include<string>
using namespace std;

//s->e
//경로중에 최솟값이 최대로 
int len = 1e9;

unordered_map<long long, long long>anum;
unordered_map<int, int>bnum;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
  
    int t, n, m;
    vector<long long>A;
    vector<long long>B;
    vector<int>a;
    vector<int>b;
    cin >> t;
    cin >> n;
    A.assign(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
        a.push_back(A[i]);
        if (i > 0)A[i] += A[i - 1];
    }
    cin >> m;
    B.assign(m, 0);
    for (int j = 0; j < m; j++) {
        cin >> B[j];
        b.push_back(B[j]);
        if (j > 0)B[j] += B[j- 1];
    }

   

    vector<long long>bsum;
    vector<long long>asum;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            asum.push_back(A[j] - A[i] + a[i]);
        }
    }

    for (int i = 0; i < m; i++) {
        for (int j = i; j < m; j++) {
            bsum.push_back(B[j] - B[i] + b[i]);
        }
    }

    sort(asum.begin(), asum.end());
    sort(bsum.begin(), bsum.end());

  
    long long  al = asum.size(); int bl = bsum.size();
    long long  ap = 0; int bp = bl-1;
    long long cnt = 0;
    
    while (bp >=0 && ap<al) {

        long long  aa = asum[ap];
        long long  bb = bsum[bp];
        //cout << ap << "," << bp << "탐새중\n";
        if ((aa + bb) == t) {
            
            //같은 숫자인거 어디까지? -> 이걸 걍 map으로 하면 좋을텐데
            
            long long  num1 = 0;
            while (ap < al && asum[ap] == aa) {
                num1++;
                ap++;
            }
            long long  num2 = 0;
            while (bp >=0 && bsum[bp] == bb) {
                num2++;
                bp--;
            }
            cnt += num1 * num2;
           // cout << num1 * num2 << "더함";
            //뭐로 넘아가??
            //뒤는 볼필요 없고,,
            
        }
        else if ((aa + bb) < t) { //작고 
            ap++; //이것도 같은 크기만큼 건너뗘야함...
        }
        else { //클때 
            bp--;
        }


    }

    cout << cnt;

    
    //다시 정리
    /*
    vector<long long>alists;
    for (int i = 0; i < asum.size(); i++) {
        if (!anum[asum[i]]) {
            alists.push_back(asum[i]);
        }
      
        anum[asum[i]]++;
    }
    

    long long al = alists.size();
    long long bl = bsum.size(); //중복 없이
     

    int ap = 0; int bp = 0;
    long long cnt = 0;
    //1  2 3
    //2 4 5 
    //배열?
  
    for (int i = 0; i < al; i++) {
        long long aa = alists[i];
        long long an = anum[alists[i]];

        auto lit = lower_bound(bsum.begin(), bsum.end(), t - aa);
        auto uit= upper_bound(bsum.begin(), bsum.end(), t - aa);
        if ((uit - lit) > 0) {
            cnt += an * (uit - lit);
        }


    }

    cout << cnt;
    */

}