APIO 2014 - Sequence

Intuition

After playing around with some arrays, you will probably find that the order of splits doesn't matter.

Why is this true?

Consider the case where $k=2$. Let the 3 arrays have sums $A$, $B$, and $C$. If you split $[A,B,C]$ into $[A],[B,C]$ and then $[A],[B],[C]$, then you get $AB+AC+BC$ points. If you split the array into $[A,B],[C]$ and then $[A],[B],[C]$ though, you still get $AB+AC+BC$ points.

A similar argument holds for $k>2$.

We have now greatly simplified our problem! Without loss of generality, assume we make splits from left to right.

Formulating a DP

First, let $p_i$ be the sum of $a_j$ for all $j\le i$.

Let $dp[i][j]$ be the maximum number of points we can get if we have made $j$ splits and the $j$-th split is between $a_i$ and $a_{i+1}$.

We have the following recurrence:

The answer is $dp[n-1][k+1]$ (assuming we make an extra split at the end of the array, which doesn't affect our answer).

Computing this naively would take $\mathcal{O}(n^{2}k)$ time, but we can do much better than that.

Using CHT

Look at the DP recurrence again. Can you see how it's effectively finding the maximum of several linear functions at a point?

We can rearrange the recurrence to become

Recall that a linear function can be defined as $y=mx+c$.

In this case, we have $m=-p_l$, $x=p_{n-1}-p_i$, and $c=dp[l][j-1]$.

This means we can use CHT (with a deque) to compute the answer in $\mathcal{O}(nk)$ - a significant improvement!

One Final Optimization

Unfortunately, if we implement this solution directly, we exceed the memory limits.

Notice how $dp[i][j]$ only depends on $dp[l][j-1]$. This means that instead of storing $k$ arrays of $dp[i]$, we can simply store two $dp$ arrays and alternate between them.

This brings the memory used down to $\mathcal{O}(n)$, which is good enough to pass.

Complexity

Time: $\mathcal{O}(nk)$.

Memory: $\mathcal{O}(n)$.

Code

1#include <bits/stdc++.h>
2#pragma GCC optimize("O3")
3#define FOR(i, x, y) for (int i = x; i < y; i++)
4typedef long long ll;
5using namespace std;
6
7int n, k;
8int where[201][100001];
9ll pref[100001]{0}, dp[2][100001], q[100001], l = 1, r = 1;
10