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

hide comments
cat_got_bored: 2016-01-01 20:10:00

I couldn't get AC with STL map anyhow .... even with optimizations :-(
Then used only arrays,and binary search and got AC!
Didn't know STL map is this slow
AND DONT TAKE THE ARRAY LONG . WILL GET YOU TLE

Last edit: 2016-01-01 20:13:07
SHIVEK SACKLECHA: 2015-12-27 21:39:58

Dont know why but long long gives a TLE and int gives an accepted solution! Strange.

Arjav Patel: 2015-12-23 16:29:48

long long => tle
int => AC

ranit: 2015-11-23 08:29:36

There is a problem. I submitted the same code twice once give me TLE other give AC. It's really funny.

Last edit: 2015-11-23 08:29:55
Lai Manh Tuan: 2015-11-03 08:43:56

Got AC by using STL (with some optimizations).
But I hate this kind of problems. Time limit is too strict. You spend more time to optimize your code than to think of algorithms.

Keshav Reddy: 2015-11-02 22:10:45

Why does std::unordered_map give TLE?

Last edit: 2015-11-02 22:10:59
xashru: 2015-10-02 01:31:08

why does using
ios_base::sync_with_stdio(false); cin.tie(0);
give WA but omitting it gets AC?

Last edit: 2015-10-02 01:31:32
ratedx: 2015-09-25 09:04:36

@Varun Gambhir both ordered and unordered are giving tle in my case!
What is your time complexity?

kobe24: 2015-09-05 00:30:06

Last edit: 2015-09-05 00:52:55
earner: 2015-08-27 18:12:06

can anyone tell why the 10th test case is giving wrong answer?


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