Table of Contents

ExplanationImplementation

Explanation

The Official Editorial uses a divide and conquer approach. However, like many divide and conquer optimization problems, this can also be solved using the convex hull trick.

First, define the following:

pre[i]=∑i=1iai\texttt{pre}[i] = \sum_{i = 1}^i a_i
ips[i]=∑i=1iai⋅i\texttt{ips}[i] = \sum_{i = 1}^i a_i \cdot i

We would like to find the score of some subarray [l,r][l, r], defined as

∑i=lrai⋅(i−l+1)\sum_{i = l}^r a_i\cdot(i - l+1)

By expanding this expression, we can express this in terms of pre\texttt{pre} and ips\texttt{ips}:

∑i=lrai⋅(i−l+1)=ips[r]−ips[l−1]−(l−1)(pre[r]−pre[l−1])\sum_{i = l}^r a_i\cdot(i - l+1) = \texttt{ips}[r]-\texttt{ips}[l-1]-(l-1)(\texttt{pre}[r]-\texttt{pre}[l-1])

For this problem, we need to choose a contiguous subarray in order to maximize the required score. Let us define a function ff, such that f(r)f(r) denotes the maximum score of a subarray that ends at rr. We can thus define ff as follows:

f(r)=max⁡1≤l≤r{ips[r]−ips[l−1]−(l−1)(pre[r]−pre[l−1])}=max⁡1≤l≤r{ips[r]−ips[l−1]−(l−1)pre[r]+(l−1)pre[l−1]}=max⁡1≤l≤r{ips[r]−ips[l−1]−l⋅pre[r]+pre[r]+l⋅pre[l−1]−pre[l−1]}=max⁡1≤l≤r{(ips[l−1]−pre[l−1]+l⋅pre[l−1])−l⋅pre[r]}+ips[r]+pre[r]\begin{align*} f(r) &= \max_{1 \leq l \leq r} \{\texttt{ips}[r] - \texttt{ips}[l - 1] - (l - 1)(\texttt{pre}[r] - \texttt{pre}[l - 1])\}\\ &=\max_{1 \leq l \leq r} \{\texttt{ips}[r] - \texttt{ips}[l - 1] - (l - 1)\texttt{pre}[r] + (l - 1)\texttt{pre}[l - 1]\}\\ &=\max_{1 \leq l \leq r} \{\texttt{ips}[r] - \texttt{ips}[l - 1] - l \cdot \texttt{pre}[r] + \texttt{pre}[r] + l \cdot \texttt{pre}[l - 1] - \texttt{pre}[l - 1]\}\\ &= \max_{1 \leq l \leq r} \{(\texttt{ips}[l - 1] - \texttt{pre}[l - 1] + l \cdot \texttt{pre}[l - 1]) - l \cdot \texttt{pre}[r]\} + \texttt{ips}[r] + \texttt{pre}[r] \end{align*}

We rearrange the equation such that terms that depend only on ll are wrapped in parenthesis inside of the max⁡\max statement and terms that depend only on rr are moved outside of the max⁡\max statement. Note that there is only a single term that depends on both ll and rr.

Because of this property, we can use the convex hull trick. Each value can be represented as a linear function of the form

gl(x)=l⋅x+(ips[l−1]−pre[l−1]+l⋅pre[l−1])g_l(x) = l \cdot x + (\texttt{ips}[l - 1] - \texttt{pre}[l - 1] + l \cdot \texttt{pre}[l - 1])

The original equation can thus be expressed as:

f(r)=max⁡1≤l≤r{gl(pre[r])}+ips[r]+pre[r]f(r) = \max_{1 \leq l \leq r} \{g_l(\texttt{pre}[r])\} + \texttt{ips}[r] + \texttt{pre}[r]

Implementation

C++

Complexity: O(nlog⁡n)\mathcal{O}(n \log n). The implementation below uses a Line Container, but it's also possible to dynamically maintain a deque and using binary search for queries by taking advantange of the monotonicity of ll.

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


 Code Snippet: Line Container (Click to expand)


const int MAXN = 2e5 + 1;


int N;
long long A[MAXN], pre[MAXN], ips[MAXN];

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