[알고리즘] 백준 2143 - 두 배열의 합 (C++)

[문제 링크] : https://www.acmicpc.net/problem/2143

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int T, N, M;
int A[1001], B[1001];
vector<int> AV, BV;

int main(){
    cin >> T;
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> A[i];
    }

    cin >> M;
    for(int i=0; i<M; i++){
        cin >> B[i];
    }
    
    for(int i=0; i<N; i++){
        int sum = A[i];
        AV.push_back(sum);
        for(int j=i+1; j<N; j++){
            sum += A[j];
            AV.push_back(sum);
        }
    }

    for(int i=0; i<M; i++){
        int sum = B[i];
        BV.push_back(sum);
        for(int j=i+1; j<M; j++){
            sum += B[j];
            BV.push_back(sum);
        }
    }

    sort(BV.begin(), BV.end());
    
    long long Ans = 0;
    for(int i=0; i<AV.size(); i++){
        int tmp = T - AV[i];
        int lo = lower_bound(BV.begin(), BV.end(), tmp) - BV.begin();
        int hi = upper_bound(BV.begin(), BV.end(), tmp) - BV.begin();
        Ans += (hi - lo);
    }

    cout << Ans << "\n";
    return 0;
}