Subtask 1

Observe that it is always optimal to grow to our final height at the beginning. Also, note that ~0~ and the elements of ~A_i~ 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 ~H~ and ~P~.

We can simulate this subtask in quadratic time.

Time Complexity: ~\mathcal O(N^2)~

Subtask 2

We need a faster simulation. Consider a given height ~x~. Let ~a_c~ be the number of elements with larger height than ~x~ in ~A~. Let ~a_t~ be the total height of the elements with larger height than ~x~ in ~A~. Then we need to pay ~Hx~ to grow to this height, and ~P(a_t - xa_c)~ as our potion total. The easiest solution is to insert a zero into the list, sort, and iterate backward.

Time Complexity: ~\mathcal O(N \log N)~

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 ~a_t~ and ~a_c~. Consider an arbitrary height ~x~ between ~A_i~ and ~A_{i + 1}~. While our height is between these two values, ~a_t~ and ~a_c~ don't choose. Consider our expression of cost from subtask 2 ~Hx + P(a_t - xa_c)~:

$$\displaystyle C = Hx + Pa_t - Pa_cx = (H - Pa_c)x + Pa_t$$

Depending on how ~H~ compares to ~Pa_c~, we either benefit from continually increasing ~x~, or continually decreasing it, until ~a_t~ and ~a_c~ change.