Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Let us denote the largest element of the input array with 
~M~ and the sum of the array with 
~S~. Let us observe the following two cases:
~M \le S/2~
The lower bound to the solution of the task is clearly ~S~ and such a solution can always be achieved in this case. If we sort the elements of the input array and denote them with integers from 
~1~ (smallest) to 
~N~ (largest), then one of the optimal arrangements is: Ante 
~\{1, 2, \dots, N\}~ and Goran 
~\{N, 1, 2, \dots, N-1\}~.
~M > S/2~
This inequality can be written as 
~M > S-M~ or, in other words, the time required for the slowest team is larger than the sum of times of all other teams.
The lower bound to the solution in this case is 
~2M~ because both lecturers have to give their lecture to the slowest team and can't do so at the same time. In this case too, it is possible to always achieve the lower bound. Let Ante first give the lecture to the slowest team, while Goran gives his lecture to all the other teams and waits for Ante to finish. After that, Goran takes over the slowest team and Ante the rest of the teams.
Comments