Sphere Online Judge

Maintanance
Because of maintenance, it won't be possible to submit any solutions this evening. The maintenance starts at 2014-12-19 19:00 GMT (20:00 SPOJ time) and will last from 8 to 10 hours.

OK, don't show this message any more


SPOJ Problem Set (classical)

1296. 4 values whose sum is 0

Problem code: SUMFOUR

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
Resource:South western 05-06

hide comments
2014-11-28 10:46:26 uttom
i got wa
http://paste.ubuntu.com/9280717/

Last edit: 2014-11-28 10:47:57
2014-11-08 15:30:09 mayank
still cannot get why map is exceeding time!
2014-11-06 16:31:25 Sudarshan K
Use library functions as much as possible.
Use arrays over vectors.
And for god's sake use only int.
Nice problem.
2014-11-02 14:55:06 Gaurav Ahirwar
great question :)
2014-06-11 13:51:00 Miguel Oliveira
very weak test cases, it doesn't even have n up to 4000
2014-06-02 13:41:18 Achut Nandam
Getting TLE for n^2 log(n) assuming map uses log(n) to search
is binary search faster than map?

Last edit: 2014-06-02 13:52:45
2014-06-01 12:48:57 new
use of long long gives TLE in my logic but
int got ac
2014-04-08 11:38:42 Nadav Chernin
What does it mean that TME was only in running "10". That sum of all 10 times exceed Time Limit? Or only 10-th run?
2014-03-03 06:09:19 [Lakshman]
@Abhishek there is a time limit,13 se is sum running time of all test cases the input file have.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.