Editorial for DMOPC '14 Contest 7 P5 - Aurora
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
The optimal solution for all soldiers to reach their destinations means
These first
After sorting the list of the destinations, we can iterate over an array containing the individual times each soldier will take and check whether it will be globally optimal to have him travel by para-mail instead. Once a soldier that would increase the total time taken if he switched to para-mail is reached, the remaining soldiers only need to be updated.
The optimal solution is the sum of all of the times in the array after this update.
Time Complexity:
Comments