This is $O(N^3)$ because we compute the total happiness of some array of winners $O(N)$ times. Each computation requires $O(N)$ days, and on each day we go through all members in the list, and the list may have up to $O(N)$ people.

Note there are easier $O(N^3^)$ solutions, we showed this one because it is easier to get to the next step with it.

Note there are easier solutions for $11$ points, we showed this one because it is easier to get to the next step with it.

h2. $O(N^2^)$

We must still treat the happiness of $0$, but it can be computed efficiently in a similar manner, using its segments of coin receiving and some partial sums.

The final complexity is $O(N)$ because we can obtain in $O(N)$ all the precomputations about $I(0)$ and $I(N)$ and we can print each of the $N + 1$ numbers using $O(1)$ time.
 
h3. Request
 
Contacteaza-l pe autor daca te oferi sa traduci enuntul in limba romana.

The final complexity is $O(N)$ because we can obtain in $O(N)$ all the precomputations about $I(0)$ and $I(N)$ and we can print each of the $N + 1$ numbers using $O(1)$ time.