Editorial for DMOPC '21 Contest 2 P1 - Bosses
Submitting an official solution before solving the problem yourself is a bannable offence.
Observe that it is always optimal to grow to our final height at the beginning. Also, note that and the elements of are the only heights we need to consider. The intuitive proof of this is that it is always better to grow more or not to grow at all, depending on and .
We can simulate this subtask in quadratic time.
We need a faster simulation. Consider a given height . Let be the number of elements with larger height than in . Let be the total height of the elements with larger height than in . Then we need to pay to grow to this height, and as our potion total. The easiest solution is to insert a zero into the list, sort, and iterate backward.
Proof of Claim
Note that since we grow to our final height at the beginning, the order of the bosses is arbitrary. Sort them. As in the second subtask, define and . Consider an arbitrary height between and . While our height is between these two values, and don't choose. Consider our expression of cost from subtask 2 :
Depending on how compares to , we either benefit from continually increasing , or continually decreasing it, until and change.