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
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...


praval_singhal:
20160531 17:32:29
@Abhilash why have you gave n=4000 when n*n<10000000. Isn't it misleading. 

candide:
20160425 10:33:17
Done in PyPy. No sort, no binary sort, only arrays. ABCDEF is very similar.


Akshay Damle:
20160412 23:17:17
AC in 1 go :D Try ABCDEF before this. Using vectors for the sums and upper_bound, lower_bound works. 

wh1t3_r0s3:
20160322 20:25:41
getting TLE on the 9th test case? what should i do?

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 