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
2018-10-17 22:57:20
unordered_map with reserve keyword got accepted

very frustating question

takeaway from this question: unordered_map is significantly faster than map and use of 'reserve' can optimize it further

Last edit: 2018-10-17 23:09:17
2018-09-29 22:51:02
Lots of optimization required:-
- don't use set in cpp
- don't use fast_io
- don't use long long int
- use equal_range instead of upper_bound and lower_bound

Last edit: 2018-09-30 12:15:25
2018-09-25 11:04:43
maps sets unordered maps nothing worked! had to write the binary search on my own!!
2018-09-04 01:45:45
how cani store integer values (with absolute value as large as 2^28 )
2018-08-21 10:08:44
applied BS but getting WA on 9 again and again!
2018-08-17 14:14:48
did you done in java?? if yes, then please help me out.!!
2018-07-30 11:36:50
is solution using lower_bound and upper_bounds?
2018-06-09 20:25:29
@vengatesh15 Yeah me too!!
2018-06-06 19:22:53
Should do with both Hash-Map and Vectors to analysise complexity
2018-03-31 13:26:01
@mahabir10 answer to your question should be 8!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.