SUMFOUR  4 values whose sum is 0
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 ) belongs to A x B x C x D are such that a + b + c + d = 0 . 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 4000). We then have n lines containing four integer values (with absolute value as large as 2^{28} ) that belong respectively to A, B, C and D .
(Edited: n <= 2500)
Output
Output should be printed on a single line.
Example
Input: 6 45 22 42 16 41 27 56 30 36 53 37 77 36 30 75 46 26 38 10 62 32 54 6 45 Output: 5
hide comments
kya_bantai:
20201008 06:16:31
after this try abcdef problem on spoj


dhruvgheewala:
20200916 09:30:15
Getting TLE only, I have used MIM + (map, unordered map with good hash fxn, binary search, C++ lower_bound & upper_bound on vector after sorting it). Still getting TLE. Anyone suggest something or any other technique. 

wille_25:
20200801 05:41:36
if you do ABCDEF problem first ...its is a piece of cake for you ...same logic; 

overthinker_72:
20200607 12:58:36
upper bound and lower bound can help :)


shivamojha99:
20200604 14:20:26
Can anyone tell me why map.find() isn't working although its complexity is log(n) too, and why using vectors get AC but not with Map function??


sandeep48:
20200604 07:30:55
(n square)log(n) is working 

brokeboy:
20200504 13:35:26
STL maps gave TLE. Use array and sort instead. 

kkkrr:
20200421 23:12:31
It can be solved using hashing. Instead of using STL try implementing your own hash map:) 

manish_thakur:
20200401 16:01:14
Since you have come to comments for help, use equal_range in c++ 

d_sm:
20200309 07:36:55
accepted in one submission , make lhs and rhs two array and then sort ,and search for each lhs the upper and lower bound in rhs..... 
Added by:  Abhilash I 
Date:  20070206 
Time limit:  1.419s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  South western 0506 