Explanation

Let $\texttt{dp}[i]$ denote the maximum effectiveness of the prefix of length $i$ of the unit. The transitions are defined as $\texttt{dp}[i] = \max_{0 \leq j < i} \{\texttt{dp}[j] + ax^2+bx+c\}$, where $x = \texttt{sum}(j + 1, i) = \sum_{k = j + 1}^i x_k$.

Define a prefix sum array $\texttt{pre}[i] = \sum_{k = 1}^i x_k$. We can then express $x$ as $\texttt{pre}[i] - \texttt{pre}[j]$. Now evaluate the first equation with our new value of $x$:

• $\texttt{dp}[i] = \max_{1 \leq j < i} \{\texttt{dp}[j] + ax^2+bx+c\}$
• $\texttt{dp}[i] = \max_{1 \leq j < i} \{\texttt{dp}[j] + a[\texttt{pre}[i] - \texttt{pre}[j]]^2+b[\texttt{pre}[i] - \texttt{pre}[j]]+c\}$
• $\texttt{dp}[i] = \max_{1 \leq j < i} \{\texttt{dp}[j] + [a\cdot\texttt{pre}[i]^2 - 2a\cdot\texttt{pre}[i]\texttt{pre}[j] + a\cdot\texttt{pre}[j]^2] + b\cdot\texttt{pre}[i]-b\cdot\texttt{pre}[j]+c\}$

We will factor terms that do not depend on $j$ outside of the $\max$ statement.

$\texttt{dp}[i] = \max_{0 \leq j < i} \{\texttt{dp}[j] - 2a\cdot\texttt{pre}[i]\texttt{pre}[j] + a\cdot\texttt{pre}[j]^2 - b\cdot\texttt{pre}[j]\} + a\cdot\texttt{pre}[i]^2 + b\cdot\texttt{pre}[i] + c$

We will group terms that depend only on $j$ with $\texttt{dp}[j]$.

$\texttt{dp}[i] = \max_{0 \leq j < i} \{(\texttt{dp}[j] + a\cdot\texttt{pre}[j]^2 - b\cdot\texttt{pre}[j]) - 2a\cdot\texttt{pre}[i]\texttt{pre}[j]\} + a\cdot\texttt{pre}[i]^2 + b\cdot\texttt{pre}[i] + c$

To efficiently handle transitions in $\mathcal{O}(\log n)$ or $\mathcal{O}(1)$, we will use the convex hull optimization.

Time Complexity: $\mathcal{O}(n \log n)$

Implementation

Copy
#include <bits/stdc++.h>
using namespace std;

// source:
// https://github.com/kth-competitive-programming/kactl/blob/main/content/data-structures/LineContainer.h
// supports insertion of linear functions and querying of MAXIMUM value of x for
// a given x for details on internal implementation, see LineContainer module
// alternatively, learn Li Chao Tree
inline namespace _LineContainer {
bool _Line_Comp_State;