Sphere Online Judge

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:10s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All except: ERL JS NODEJS PERL 6
Resource:South western 05-06

hide comments
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 DEVENDRA
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.
2014-03-03 05:13:48 Abhishek Subal
i DON'T THINK THERE IS ANY TIME LIMIT MY 13 SEC SOLUTION PASSED
2014-02-12 16:57:42 mrolympia
AC in one go :) very similar to ANARC05B, int is enough...
2014-02-11 17:27:19 Daga
choose correct data types
vectors instead of arrays and long instead of long long
2014-02-08 10:37:45 Java Jambavan
i cudnt understand the question
2013-12-17 19:32:32 Yash
Getting Wrong Answer on running "10"..
Any missing test case...
plz help..
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.