Four Sum

All submissions for this problem are available.
In this problem you are given a sequence of $N$ positive integers $S[1],S[2],\dots,S[N]$. In addition you are given an integer $T$, and your aim is to find the number of quadruples $(i,j,k,l)$, such that $1 \le i < j < k < l \le N$, and $S[i] + S[j] + S[k] + S[l] = T$. That is, the number of ways of picking four numbers from the sequence summing up to $T$. ### Constraints: For all test cases,  $1 \le N \le 5000$  $1 \le T \le 10^6$  $1 \le S[i] \le 10^9$, for all $i$. Subtask $1:10\%$ It is guaranteed that $N \le 50$. Subtask $2:50\%$ It is guaranteed that $N \le 300$. Subtask $3:40\%$ No additional guarantees. ### Input Format: There is only one line of input with $N+2$ space separated integers. The first two integers are $N$ and $T$. The next $N$ integers are $S[1],S[2],\dots,S[N]$. ### Output Format: A single integer which is the number of valid quadruples. ### Sample Input 1: ```6 20 3 1 1 2 5 10``` ### Sample Output 1: ```1``` ### Explanation 1: The quadruple $(1,4,5,6)$ is valid because $S[1]+S[4]+S[5]+S[6]=3+2+5+10=20$. You can check that no other quadruple is valid and hence the answer is $1$. ### Sample Input 2: ```6 13 1 2 3 4 5 4``` ### Sample Output 2: ```3``` ### Explanation 2: You can verify that the only quadruples that are valid are $(2,3,4,6),(1,3,4,5)$ and $(1,3,5,6)$. Thus, the answer is $3$. ### Note: As the answer might be large, please use 64 bit integers (`long long int` in C/C++ and `long` in Java) instead of 32 bit int.Author:  admin3 
Date Added:  29112018 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions