Description
The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c, d ) ∈ A x B x C x D are such that a + b + c + d = . In the following, we assume that all lists have the same size n .
Input
The first line of the input file contains the size of the lists n (this value can be as large as ). We then have n lines containing four integer values (with absolute value as large as ) that belong respectively to A, B, C and D .
Output
For each input file, your program has to write the number quadruplets whose sum is zero.
Sample Input
- -
- -
- -
- - -
- -
- - -
Sample Output
Hint
Sample Explanation: Indeed, the sum of the five following quadruplets is zero: (-, -, , ), (, , -, -), (-, , , -),(-, , -, ), (-, -, , ).
AC代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;
#define ll long long
#define N 4006
int n;
int mp[N][N];
int A[N],B[N],C[N],D[N];
int CD[N*N];
void solve(){
for(int i=;i<n;i++){
for(int j=;j<n;j++){
CD[i*n+j]=C[i]+D[j];
}
}
sort(CD,CD+n*n);
ll ans=;
for(int i=;i<n;i++){
for(int j=;j<n;j++){
int cd = -(A[i]+B[j]);
ans+=upper_bound(CD,CD+n*n,cd)-lower_bound(CD,CD+n*n,cd);
}
}
printf("%I64d\n",ans);
}
int main()
{
while(scanf("%d",&n)==){
for(int i=;i<n;i++){
for(int j=;j<;j++){
scanf("%d",&mp[i][j]);
}
}
for(int i=;i<n;i++){
A[i] = mp[i][];
B[i] = mp[i][];
C[i] = mp[i][];
D[i] = mp[i][];
}
solve();
}
return ;
}