Function optimization P85038


Statement
 

pdf   zip   main.cc

html

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 105, and that the elements of the vectors are all between 1 and 108.

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