## 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
 mikroz: 2019-04-13 13:19:50 gp_hash_table sagar_june97p: 2019-04-12 20:07:25 unordered_map got me TLE, however equal_range passed. prudhvi_495: 2019-04-07 13:20:45 Last edit: 2019-04-14 08:06:25 syed_tanveer: 2019-04-03 12:40:58 AC in first go using upper_bound() and lower_bound() Rahul Kathuria: 2019-04-03 03:44:13 Easy peasy :P AC in 1st go! No need of equal range, hint :- just use vector with int data type and brute force(double pointer) in n^2 :) divik544: 2019-03-27 15:51:02 1. Do not remove duplicates. 2. Use unordered_map with reserve Mine passed in 2.34 s y17prashant: 2019-03-22 02:30:56 use vectors , array gave a RE.......fast io worked here .....Hint- Complexity O(n^2*log(k))........Simple one Last edit: 2019-03-22 02:33:16 alphacoder101: 2019-02-06 05:31:00 This is what happened for me: Using map got TLE Using unordered_map got TLE Using unordered_map with reserved got TLE Using Vectors wit h lower and upper_bound got TLE Using arrays with lower and upper_bound got TLE Using arrays with equal_range got accepted. Many got AC with bounds and unordered_map. But they didnt work for me. masterchef2209: 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 mayank_soni055: 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

 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