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-x{a}_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-x{a}_c)$:

$${\displaystyle C=Hx+P{a}_t-P{a}_{c}x=(H-P{a}_c)x+P{a}_t}$$

Depending on how $H$ compares to $P{a}_c$, we either benefit from continually increasing $x$, or continually decreasing it, until $a_t$ and $a_c$ change.