Solution 1

$\mathcal{O}(n^3)$: Using dynamic programming, let $f(n)$ indicate the maximum battle effectiveness after adjustment. We have transfer equations below:

$${\displaystyle f(n)=\underset{0\le i<n}{max}\{f(i)+g\left(\sum _{j=i+1}^n{X}_j\right)\},g(x)=A{x}^2+Bx+C}$$

Such a solution should score around $20\mathrm{\%}$.

Solution 2

$\mathcal{O}(n^2)$: Use pre-calculated partial sum to accelerate the solution above. Let $S_i=\sum _{i=1}^n{X}_i$, we have $f(n)=\underset{0\le i<n}{max}\{f(i)+g(S_n-S_i)\}$.

Such a solution should score around $50\mathrm{\%}$.

Solution 3

$\mathcal{O}(n)$: Consider two decisions $i<j$, we choose $i$ instead of $j$ if and only if:

$${\displaystyle \begin{array}{rl}& f(i)+g(S_n-S_i)>f(j)+g(S_n-S_j)⟺\\ & g(S_n-S_i)-g(S_n-S_j)>f(j)-f(i)⟺\\ & A((S_n-S_i{)}^2-(S_n-S_j{)}^2)+B((S_n-S_i)-(S_n-S_j))>f(j)-f(i)⟺\\ & A(2S_n-S_i-S_j)(S_j-S_i)+B(S_j-S_i)>f(j)-f(i)⟺\\ & A(2S_n-S_i-S_j)+B>\frac{f(j)-f(i)}{S_j-S_i}⟺\\ & 2S_n<\frac{1}{A}(\frac{f(j)-f(i)}{S_j-S_i}-B)+S_i+S_j\end{array}}$$

Thus, we can use a queue holding all necessary decisions. Each decision in the queue is the best decision during a specific range of $S_n$. When a decision is to be made, we simply begin searching at one end of the queue, and find the first decision where $S_n$ is in its range. After that, we put decision $N$ at the other end of the queue as a new decision, updating the range of decisions before it using the inequality above.

Such a solution should score $100\mathrm{\%}$.