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) = \max_{0 \le i < n} \left\{f(i)+g\left(\sum_{j=i+1}^n X_j\right)\right\}, g(x) = Ax^2+Bx+C$$

Such a solution should score around ~20\%~.

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) = \max_{0 \le i < n} \{f(i)+g(S_n-S_i)\}~.

Such a solution should score around ~50\%~.

Solution 3

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

$$\displaystyle \begin{align*} & f(i)+g(S_n-S_i) > f(j)+g(S_n-S_j) \iff \\ & g(S_n-S_i)-g(S_n-S_j) > f(j)-f(i) \iff \\ & A\left((S_n-S_i)^2-(S_n-S_j)^2\right)+B((S_n-S_i)-(S_n-S_j)) > f(j)-f(i) \iff \\ & A(2S_n-S_i-S_j)(S_j-S_i)+B(S_j-S_i) > f(j)-f(i) \iff \\ & A(2S_n-S_i-S_j)+B > \frac{f(j)-f(i)}{S_j-S_i} \iff \\ & 2S_n < \frac 1 A \left(\frac{f(j)-f(i)}{S_j-S_i}-B\right)+S_i+S_j \end{align*}$$

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\%~.