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


nonushikhar:
20160311 18:11:47
hint: sort() is faster than qsort()


prateek1985:
20160224 12:06:40
n^2 logn in java is giving TLE !! 

Rehas Mehar Kaur Sachdeva:
20160108 12:29:57
Can someone please give a hint how to optimise unordered_map based solution, no long long int used, n^2logn algorithm, no cin cout used..... 

cat_got_bored:
20160101 20:18:12
while doing binary search remember that the value can appear multiple times. 

cat_got_bored:
20160101 20:10:00
I couldn't get AC with STL map anyhow .... even with optimizations :(


SHIVEK SACKLECHA:
20151227 21:39:58
Dont know why but long long gives a TLE and int gives an accepted solution! Strange. 
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 