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 \leq 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^2k)$ 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.

Implementation

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

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

Copy
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int n, k;
int where[201][100001];
ll pref[100001]{0}, dp[2][100001], q[100001], l = 1, r = 1;

bool case1(int x, int y, int i) {