Yet Another Partiton Problem
Contest: Educational Codeforces Round 66 (Rated for Div. 2)
Difficulty rating: 3000
Tags: data structures, divide and conquer, dp, geometry, two pointers

You are given array $$$a_1, a_2, \dots, a_n$$$. You need to split it into $$$k$$$ subsegments (so every element is included in exactly one subsegment).

The weight of a subsegment $$$a_l, a_{l+1}, \dots, a_r$$$ is equal to $$$(r - l + 1) \cdot \max\limits_{l \le i \le r}(a_i)$$$. The weight of a partition is a total weight of all its segments.

Find the partition of minimal weight.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^4$$$, $$$1 \le k \le \min(100, n)$$$) — the length of the array $$$a$$$ and the number of subsegments in the partition.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^4$$$) — the array $$$a$$$.

Output format:
Print single integer — the minimal weight among all possible partitions.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Note:
The optimal partition in the first example is next: $$$6$$$ $$$1$$$ $$$7$$$ $$$\bigg|$$$ $$$4$$$.

The optimal partition in the second example is next: $$$6$$$ $$$\bigg|$$$ $$$1$$$ $$$\bigg|$$$ $$$7$$$ $$$4$$$.

One of the optimal partitions in the third example is next: $$$5$$$ $$$\bigg|$$$ $$$1$$$ $$$5$$$ $$$\bigg|$$$ $$$1$$$ $$$\bigg|$$$ $$$5$$$.

Example input:
4 2
6 1 7 4

Example output:
25

Example input:
4 3
6 1 7 4

Example output:
21

Editorial:
Important note: the author solution is using both linear Convex hull trick and persistent Li Chao tree. As mentioned in commentaries, applying the Divide-and-Conquer technique can help get rid of Li Chao tree. More about both structures you can read in this article.
Let's try to write standard dp we can come up with (arrays will be 0-indexed). Let $$$dp[k][i]$$$ be the minimal weight if we splitted prefix of length $$$i$$$ in $$$k$$$ subsegments. Then we can calculate it as: $$$dp[k][i] = \min\limits_{0 \le j < i}(dp[k - 1][j] + (i - j) \cdot \max\limits_{j \le k < i}(a[k]))$$$ [1]. Maximums on segments are inconvenient, let's try to group segments $$$[j, i)$$$ by the value of $$$\max{}$$$.
So, we can find such sequence of borders $$$j_0 = i - 1 > j_1 > j_2 > \dots$$$, where for each $$$j \in (j_{l + 1}, j_l]$$$ $$$\max\limits_{j \le k < i}(a[k]) = a[j_l]$$$. In other words, $$$j_0 = i - 1$$$ and $$$j_{l + 1}$$$ is the closest from the left position, where $$$a[j_{l + 1}] \ge a[j_l]$$$. Note, that we can maintain this sequence with stack of maximums.
Ok, then for each interval $$$(j_{l + 1}, j_l]$$$ equation [1] transforms to: $$$$$$\min_{j_{l+1} < j \le j_l}(dp[k - 1][j] + (i - j) \cdot a[j_l]) = a[j_l] \cdot i + \min_{j_{l+1} < j \le j_l}(-j \cdot a[j_l] + dp[k - 1][j]) = \\ = a[j_l] \cdot y + \min_{j_{l+1} < j \le j_l}(-j \cdot x + dp[k - 1][j]) |_{y = i, x = a[j_l]}.$$$$$$
Why did we use variables $$$x$$$ and $$$y$$$? Because there are two problems: $$$y$$$ is needed because we iterate over $$$i$$$ and can't recalculate everything; $$$x$$$ is needed because sequence $$$j_l$$$ is changing over time, so do the $$$a[j_l]$$$. But what we can already see: we can maintain for each segment Convex hull with linear functions — so we can take $$$f_l = \min\limits_{j_{l+1} < j \le j_l}(\dots)$$$ in logarithmic time. Moreover, we can store values $$$a[j_l] \cdot y + f_l$$$ in other Convex hull to take minimum over all segments in logarithmic time.
The problems arise when we try modificate structures while iterating $$$i$$$. Fortunately, segments $$$j_l$$$ change not at random, but according to stack of maximums. So all we should handle are:
• to merge segment on top of the stack $$$(j_1, j_0]$$$ with current segment $$$(j_0, i]$$$ (in case when $$$a[i] > a[j_0]$$$);
• to erase segment on top of the stack along with its value $$$a[j_0] \cdot y + f_0$$$;
• to insert new segment on top of the stack along with its value $$$a[j_0] \cdot y + f_0$$$.
To handle the third type is easy, since all Convex hulls can insert elements. There will be at most $$$O(n)$$$ such operations on a single layer $$$k$$$ and we can ask value $$$f_0$$$ in $$$O(\log{n})$$$ and insert a line with $$$O(\log{A})$$$.
To handle the second type is harder, but possible, since we can make Convex hull persistent and store its versions in the stack. Persistent Convex hull — persistent Li Chao tree. There will be also $$$O(nk)$$$ operations in total and they cost us $$$O(1)$$$.
To handle the first type is trickiest part. Note, that all line coefficients of one convex hull are strictly lower than all line coefficients of the other. So, we can use linear Convex hulls to make insertions to back in amortized $$$O(1)$$$. But to merge efficiently, we should use Small-to-Large technique, that's why we should be able also push front in $$$O(1)$$$, and, moreover, still be able to ask minimum in $$$O(\log{n})$$$. And here comes the hack — $$$deque$$$ in C++, which can push/pop front/back in amortized $$$O(1)$$$ and also have random access iterator to make binary search possible. So, each element of every segment will be transfered $$$O(\log{n})$$$ times with cost of amortized $$$O(1)$$$ on a single layer $$$k$$$.
In the end, result complexity is $$$O(n k (\log{C} + \log{n}))$$$. Space complexity is $$$O(n \log{A})$$$.