[ BOJ 2143 ] 두배열의 합

http://icpc.me/2143

문제

배열 A와 B가 주어진다. 부분배열을 Ai,Ai+1,....,Aj로 정의내릴 때

A와 B의 부분배열의 합이 T가 되는 경우의 수를 찾아라

풀이

둘다 1000보다 작으므로 $O(N^2logN)$에 풀 수 있다.

미리 A의 부분배열의 합을 map에 다 저장해놓은 다음에, B의 부분배열을 순회하면서 T에서 뺸 값이 존재하는지 확인한다.

존재하면 더해주는 식으로 진행

답의 범위가 int를 넘어갈 수 있다($\approx1000\times1000\times1000\times1000=10^{12}$)

답을 long long로 해야한다는거에 조심하자

코드

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
map<int,int> mp;
int an[1005],bn[1005],parta[1005],partb[1005];
int main()
{
    int T; scanf("%d",&T);
    int n; scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&an[i]);
    int m; scanf("%d",&m);
    for(int i=0;i<m;i++) scanf("%d",&bn[i]);
    for(int i=1;i<=n;i++) parta[i]=parta[i-1]+an[i-1];
    for(int i=1;i<=m;i++) partb[i]=partb[i-1]+bn[i-1];
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<i;j++) mp[parta[i]-parta[j]]++;
    }
    ll ans=0;
    for(int i=1;i<=m;i++)
    {
        for(int j=0;j<i;j++) if(mp.count(T-(partb[i]-partb[j]))!=0) ans+=mp[T-(partb[i]-partb[j])];
    }
    return !printf("%lld",ans);
}