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; }
잘 참고 하고 갑니다~
답글삭제로직을 항상 잘 정리해 놓으시네요! 부럽습니다 ㅎㅎ