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
souvik23:
20170125 21:04:49
Simple O((n^2)logn) using unordered_map without calling "reserve" function. 

vunnamtej:
20170125 17:57:44
thanks to @Shubham Gupta 

Mohammad_Ali:
20160901 02:34:38
For those of you using unordered_map, it would be useful to call m.reserve(2*n*n). 

TP:
20160714 11:41:57
Don't use long long . It costs me 2 TLE . 

mkfeuhrer:
20160710 22:03:37
nice problem!! only stl ie sort upper bound and lower bound gave TLE ! got AC using two pointer approach after O(n*n) sum calculations! 

Anuj Arora:
20160710 17:35:18
AC in one shot :D 

Shubham Gupta:
20160706 23:55:06
If getting TLE with std::lower_bound and std::upper_bound, then try using std::equal_range!


priyanshu_02:
20160624 00:54:02
Don't use binary search or stl bound functions.


kartikay singh:
20160622 12:50:39
@praval_singhal


begin_88:
20160611 13:54:51
getting tle even after using int, vectors, lb, ub, check for same values...

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 