Trouble
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2961 Accepted Submission(s): 893
Problem Description
Hassan is in trouble. His mathematics teacher has given him a very difficult problem called 5-sum. Please help him. The 5-sum problem is defined as follows: Given 5 sets S_1,...,S_5 of n integer numbers each, is there a_1 in S_1,...,a_5 in S_5 such that a_1+...+a_5=0?
Input
First line of input contains a single integer N (1≤N≤50). N test-cases follow. First line of each test-case contains a single integer n (1<=n<=200). 5 lines follow each containing n integer numbers in range [-10^15, 1 0^15]. I-th line denotes set S_i for 1<=i<=5.
Output
For each test-case output "Yes" (without quotes) if there are a_1 in S_1,...,a_5 in S_5 such that a_1+...+a_5=0, otherwise output "No".
Sample Input
2 2 1 -1 1 -1 1 -1 1 -1 1 -1 3 1 2 3 -1 -2 -3 4 5 6 -1 3 2 -4 -10 -1
Sample Output
No Yes
1 //大致题意：判断五个数之和是否可能为0 2 #include3 #include 4 #include 5 using namespace std; 6 7 typedef __int64 LL;//用define时出了错误 8 LL a[210]; 9 LL b[210];10 LL c[210];11 LL f[202*202];12 LL g[202*202];13 int num;14 15 int main()16 {17 int i,j,k,T;18 cin>>T;19 while(T --)20 {21 cin>>num;22 //memset(f, 0, sizeof f);23 //memset(g, 0, sizeof g);24 int cnt1 = 0;25 int cnt2 = 0;26 for(i = 0; i < num; i ++) 27 cin>>a[i];28 for(i = 0; i < num; i ++) 29 cin>>b[i];30 for(i = 0; i < num; i ++)31 for(j = 0; j < num; j ++)32 f[cnt1++] = a[i] + b[j];33 for(i = 0; i < num; i ++) 34 cin>>a[i];35 for(i = 0; i < num; i ++) 36 cin>>b[i];37 for(i = 0; i < num; i ++)38 for(j = 0; j < num; j ++)39 g[cnt2++] = a[i] + b[j];40 for(i = 0; i < num; i ++) 41 cin>>c[i];42 sort(f, f + cnt1);43 sort(g, g + cnt2);44 sort(c, c + num);45 bool flag = 0;46 for(i = 0; i < num; i ++)47 {48 LL temp = c[i];49 j = 0;50 k = cnt2 - 1;51 while(j < cnt1 && k >= 0)52 {53 if(f[j] + g[k] == (-temp))54 {55 flag = 1;56 break;57 }58 if(f[j] + g[k] <(-temp)) 59 j++;60 else 61 k--;62 }63 }64 if(flag)65 cout<<"Yes"<