## Editorial for DMOPC '21 Contest 2 P1 - Bosses

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.

Author: Riolku

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 .

Time Complexity:

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.

Time Complexity:

##### 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.