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

(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
aman224: 2017-05-24 10:47:06

sas1905 pro /\

sas1905: 2017-05-23 16:00:22

TLE with bounds ..AC with equal_range

anroc: 2017-04-18 00:39:58

You can do it in 0.08s by using Feynman's algorithm.

epsilonalpha: 2017-04-18 00:02:30

TLE with lower bound and upper bound.
A/C with equal_range and unordered_map + reserve!

amandal799: 2017-03-24 21:57:49

simple sorting and equal_range ...AC in one go

scorpion_ajay: 2017-03-18 17:22:59

its just simple.... just upper_bound and lower_bound thats it!
AC in second go ;)

anroc: 2017-03-10 06:22:55

Last edit: 2017-04-24 23:33:14
nilabja16180: 2017-03-09 16:33:58

use equal_range, if you get TLE with lower and upper bound!

sonudoo: 2017-02-05 12:24:33

If using unordered_map, choose C++14(g++ 5.1) as compiler.

up79: 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 !


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