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

(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

Added by:Abhilash I
Date:2007-02-06
Time limit:1.419s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:South western 05-06

hide comments
2017-02-05 12:24:33
If using unordered_map, choose C++14(g++ 5.1) as compiler.
2017-01-30 09:19:06
o(n^2) simple logic give you TLE :( but when u use "reserve" keyword for ur unordered map it is going to be accepted :( dont know why ! but finally AC !
2017-01-25 21:04:49
Simple O((n^2)logn) using unordered_map without calling "reserve" function.
2017-01-25 17:57:44
thanks to @Shubham Gupta
2016-09-01 02:34:38 Mohammad_Ali
For those of you using unordered_map, it would be useful to call m.reserve(2*n*n).
2016-07-14 11:41:57 TP
Don't use long long . It costs me 2 TLE .
2016-07-10 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!
2016-07-10 17:35:18 Anuj Arora
AC in one shot :D
2016-07-06 23:55:06 Shubham Gupta
If getting TLE with std::lower_bound and std::upper_bound, then try using std::equal_range!
long long is not required.
O(n^2logn) passing!
2016-06-24 00:54:02
Don't use binary search or stl bound functions.
Instead use two pointers technique to find frequencies .
Passes without optimisations.

Last edit: 2016-06-24 01:08:15
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.