I think that Integer is enough for computations in this problem. Maybe only for result we need Long.
In fact, changing all the integers to longs doesn't help, still getting WA.
What about size of arrays - it can increase dynamically, but I have set initial capacity to 10^6 = 100 ^ 3 (number of tuples (a, b, c)).
Here is my code:
import java.util.List;
import java.util.Scanner;
import java.io.OutputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
Scanner in = new Scanner(inputStream);
PrintWriter out = new PrintWriter(outputStream);
ABCDEF solver = new ABCDEF();
solver.solve(1, in, out);
out.close();
}
}
class ABCDEF {
public void solve(int testNumber, Scanner in, PrintWriter out) {
int n;
n = in.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) {
a[i] = in.nextLong();
}
ArrayList<Long> left = new ArrayList<Long>(1000000);
ArrayList<Long> right = new ArrayList<Long>(1000000);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
left.add(a[i] * a[j] + a[k]);
if (a[i] != 0) {
right.add(a[i] * (a[j] + a[k]));
}
}
}
}
Collections.sort(left);
Collections.sort(right);
int lIndex = 0, rIndex = 0;
long res = 0;
while (lIndex < left.size() && rIndex < right.size()) {
if (left.get(lIndex) == right.get(rIndex)) {
long lSize = 0;
long lEl = left.get(lIndex);
long rSize = 0;
long rEl = right.get(rIndex);
do {
++lSize;
++lIndex;
} while (lIndex < left.size() && left.get(lIndex) == lEl);
do {
++rSize;
++rIndex;
} while (rIndex < right.size() && right.get(rIndex) == rEl);
res += lSize * rSize;
} else if (left.get(lIndex) < right.get(rIndex)) {
++lIndex;
} else {
++rIndex;
}
}
out.println(res);
}
}