Table of Contents

ExplanationImplementation

Explanation

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

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

  • dp[i]=max⁡1≤j<i{dp[j]+ax2+bx+c}\texttt{dp}[i] = \max_{1 \leq j < i} \{\texttt{dp}[j] + ax^2+bx+c\}
  • dp[i]=max⁡1≤j<i{dp[j]+a[pre[i]−pre[j]]2+b[pre[i]−pre[j]]+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\}
  • dp[i]=max⁡1≤j<i{dp[j]+[a⋅pre[i]2−2a⋅pre[i]pre[j]+a⋅pre[j]2]+b⋅pre[i]−b⋅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 jj outside of the max⁡\max statement.

dp[i]=max⁡0≤j<i{dp[j]−2a⋅pre[i]pre[j]+a⋅pre[j]2−b⋅pre[j]}+a⋅pre[i]2+b⋅pre[i]+c\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 jj with dp[j]\texttt{dp}[j].

dp[i]=max⁡0≤j<i{(dp[j]+a⋅pre[j]2−b⋅pre[j])−2a⋅pre[i]pre[j]}+a⋅pre[i]2+b⋅pre[i]+c\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 O(log⁡n)\mathcal{O}(\log n) or O(1)\mathcal{O}(1), we will use the convex hull optimization.

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

Implementation

C++

#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;

Alternative Solution

The above solution uses Line Container. Using a deque, it is possible to solve this problem in O(n)\mathcal{O}(n) time although this is not necessary. See the Convex Hull Trick for more details.

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on GitHub.
  • Linear time solution using deque and convex hull trick

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum