P3648 [APIO2014] Split the Sequence

You are playing a game on a sequence of non-negative integers of length $n$. In this game, you need to split the sequence into $k + 1$ non-empty blocks. To obtain $k + 1$ blocks, repeat the following operation $k$ times: - Choose a block that has more than one element (initially, you have a single block, i.e., the entire sequence). - Choose two adjacent elements and split this block between them into two non-empty blocks. - After each operation, you gain a score equal to the product of the sums of elements in the two newly created blocks. You want to maximize the final total score.

The first line contains two integers $n$ and $k$. It is guaranteed that $k + 1 \leq n$. The second line contains $n$ non-negative integers $a_1, a_2, \cdots, a_n$ ($0 \leq a_i \leq 10^4$), representing the sequence described above.

On the first line, output the maximum total score you can obtain. On the second line, output $k$ integers between $1$ and $n - 1$, indicating the positions where you split between two elements in each operation to maximize the total score. The $i$-th integer $s_i$ means that at the $i$-th operation you split between positions $s_i$ and $s_i + 1$. If there are multiple optimal solutions, output any of them.

You can obtain a score of $108$ by the following operations: Initially, you have one block $(4, 1, 3, 4, 0, 2, 3)$. Split after the 1st element to gain $4 \times (1 + 3 + 4 + 0 + 2 + 3) = 52$ points. You now have two blocks $(4), (1, 3, 4, 0, 2, 3)$. Split after the 3rd element to gain $(1 + 3) \times (4 + 0 + 2 + 3) = 36$ points. You now have three blocks $(4), (1, 3), (4, 0, 2, 3)$. Split after the 5th element to gain $(4 + 0) \times (2 + 3) = 20$ points. Therefore, after these operations you obtain four blocks $(4), (1, 3), (4, 0), (2, 3)$ and a total score of $52 + 36 + 20 = 108$. Constraints: - Subtask 1 (11 points): $1 \leq k < n \leq 10$. - Subtask 2 (11 points): $1 \leq k < n \leq 50$. - Subtask 3 (11 points): $1 \leq k < n \leq 200$. - Subtask 4 (17 points): $2 \leq n \leq 1000$, $1 \leq k \leq \min\{n - 1, 200\}$. - Subtask 5 (21 points): $2 \leq n \leq 10000$, $1 \leq k \leq \min\{n - 1, 200\}$. - Subtask 6 (29 points): $2 \leq n \leq 100000$, $1 \leq k \leq \min\{n - 1, 200\}$. Thanks to @larryzhong for providing strengthened testdata. Translated by ChatGPT 5