Consider this function:

int mistery(const vector<int>& A, const vector<int>& B) {
int n = A.size();
int res = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (A[i] != A[j]) res = max(res, B[i] + B[j]);
return res;
}

Implement an alternative function, with the same name, return type and parameters, that computes the same, but as efficiently as possible.

Precondition

Assume that *A* and *B* have the same number *n* of elements,
that *n* is between 1 and 10^{5},
and that the elements of the vectors are all between 1 and 10^{8}.

Observation You only need to submit the required procedure; your main program will be ignored.

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Setzè Concurs de Programació de la UPC - Semifinal
- Date
- 2018-06-20