Without the restriction by \(M\), the problem can be solved as follows.

• For each \(1 \leq i \leq N\), let \(sum(i)\) be the sum of the last \(i\) terms of \(A\). Also, let \(m\) be the \(i\) that maximizes \(sum(i)/i\). Then, let the first \(N-m\) terms of \(x\) be \(0\), and the last \(m\) terms \(S/m\).

We can prove the validity of this as follows. Assume that there is an optimal solution \(x\) such that \(x_i < x_{i+1}\) (\(0 \leq i \leq N-1\)) for some \(i\) other than \(i = N-m\). Here, we assume \(x_0=0\) for convenience and take \(i=0\) into account. Now, let \(d=x_{i+1}-x_i\). By subtracting \(d\) from the last \(N-i\) terms of \(x\) and then adding \(d \times (N-i)/m\) to the last \(m\) terms of \(x\), we can have less indices \(i\) such that \(x_i < x_{i+1}\) while maintaining the sum of \(x\) and without decreasing the score. Repeating this operation results in the aforementioned form of \(x\) where the last \(m\) terms are \(S/m\).

Let us consider the restriction by \(M\). By an argument similar to the above, we can see the following:

• if \(S/m \leq M\), the optimal solution is to make the last \(m\) terms \(S/m\);
• if \(S/m > M\), it is fine to assume that the last \(m\) terms of the optimal sequence are \(M\).

For the former case, the score can be easily found. For the latter case, the optimal solution can be found by simply solving the same problem for a smaller sequence with \(N-m\) terms.

A naive implementation of this procedure leads to an \(O(N^2)\)-time algorithm, which is fast enough.

Bonus: the problem can be solved in \(O(N)\) by carefully observing the algorithm above. (Hint: convex hull)