Optimize The Slow Code
All submissions for this problem are available.
Chef hates unoptimized codes and people who write such codes. One fine day he decided to look through the kitchen's codebase and found a function whose pseudo-code is given here:
input: integer N, list X[1, 2, ..., N], list Y[1, 2, ..., N] output: integer res function: set res = 0; for i := 1 to N do for j := 1 to N do for k := 1 to N do if (X[i] = X[j]) OR (X[j] = X[k]) OR (X[k] = X[i]) continue else set res = max(res, Y[i] + Y[j] + Y[k]) return res
Luckily enough this code gets triggered only if the Head Chef makes a submission. But still there is a possibility that this can crash the judge. So help Chef by writing a new function which does the same thing but is faster.
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains an integer N denoting the number of elements in the two lists.
- The i-th of the next N lines contains a pair of space-separated integers denoting the values of X[i] and Y[i] respectively.
For each test case, output an integer corresponding to the return value of the function.
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 105
- 1 ≤ X[i], Y[i] ≤ 108
Input 2 3 1 3 3 1 1 2 5 1 3 2 4 1 2 3 2 3 4 Output 0 11
Testcase 2: The maximum is attained when i = 1, j = 2 and k = 5. This leads to res being 3 + 4 + 4 = 11. This value is attained in other iterations as well, but it never exceeds this, and hence this is the answer.
|Tags||admin2, gwr17rol, simple, sorting|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6|
Fetching successful submissions
If you are still having problems, see a sample solution here.