Hide
Problem E
Explosive Elixirs
A wizard has $N$ potions lined up on a shelf. Potion $i$ has a potency of $p_i$. She needs to organize them into exactly $K$ contiguous groups for storage. When potions are stored together they react, and the instability of a group is the sum of $(p_i - p_j)^2$ over all pairs $i < j$ in the group.
Help the wizard partition the potions into $K$ contiguous groups so that the total instability is minimized.
Input
The first line contains two integers $N$ and $K$.
The second line contains $N$ integers $p_1, p_2, \ldots , p_N$.
Output
Output a single integer: the minimum total instability.
Limits
-
$1 \leq K \leq \min (N, 200)$
-
$1 \leq N \leq 50\, 000$
-
$1 \leq p_i \leq 10\, 000$
| Sample Input 1 | Sample Output 1 |
|---|---|
4 2 3 1 4 1 |
13 |
| Sample Input 2 | Sample Output 2 |
|---|---|
6 3 1 2 10 11 20 21 |
3 |
