2143번: 두 배열의 합

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


$O(n^2\lg n)$

A,B의 부 배열의 합을 모두 구해놓고 이진 탐색으로 합이 T가 되는 쌍의 개수를 구한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int t, s[500500], cnt, s1[1001], s2[1001], n, m;
long long r;
int main() {
        scanf("%d%d", &t, &n);
        for (int i = 1; i <= n; i++) {
                scanf("%d", s1 + i);
                s1[i] += s1[i - 1];
                for (int j = 0; j < i; j++) s[cnt++] = s1[i] - s1[j];
        }
        sort(s, s + cnt);
        scanf("%d", &m);
        for (int i = 1; i <= m; i++) {
                scanf("%d", s2 + i);
                s2[i] += s2[i - 1];
                for (int j = 0; j < i; j++)
                    r += upper_bound(s, s + cnt, t - s2[i] + s2[j]) - lower_bound(s, s + cnt, t - s2[i] + s2[j]);
        }
        printf("%lld", r);
        return 0;
}