SUMFOUR - 4 values whose sum is 0

no tags 

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 228 ) that belong respectively to A, B, C and D .

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

Added by:Abhilash I
Date:2007-02-06
Time limit:1.419s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Languages:All except: ERL JS NODEJS PERL 6 SCM chicken VB.net
Resource:South western 05-06

hide comments
kshitij tripathi: 2015-06-30 14:47:43

Nice Question..don't use Long Long int !! :D

Varun Gambhir: 2015-06-23 21:11:15

Ordered map in c++ gives TLE and unordered gives AC(after some optimisations). Finally AC. :D

Last edit: 2015-06-23 21:11:36
sameer makker: 2015-06-20 18:20:15

Can anybody explain why unordered_map fails here ?
Got a lot of TLEs, finally got AC. But still not sure why those solutions failed !

Dhruv Mullick: 2015-06-20 16:01:50

Optimisations needed.

Ayur Jain: 2015-06-20 10:55:09

Passes in O(n^2logn). Don't use STLs.

sujit yadav: 2015-06-19 00:31:13

take 2 pointer array in pair stl ....learn a lot .. thanks !!! :)

bsaha205: 2015-06-16 22:13:57

can you tell the tenth case??
it is giving wrong ans :( :(

xxbloodysantaxx: 2015-06-08 20:48:58

Time Limit is too strict will make you cry!

kirakira: 2015-06-08 04:53:20

damn i almost cry for not AC such "easy" problem :(
Do not use long long, do not use binary search, in my case, I even cannot use STL::vector / map / set, etc.

i_am_looser: 2015-05-08 15:19:09

STL - took 5 minute to get AC : )