Description

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.

Input Format

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.

Output Format

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.

7 3
4 1 3 4 0 2 3

108
1 3 5

Hint

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