Problem M
Split the Sequence
You are playing a game with a sequence of $n$ non-negative integers. In this game you have to split the sequence into $k+1$ non-empty parts. To obtain $k+1$ parts you repeat the following steps $k$ times:
-
Choose any part with more than one element (initially you have only one part – the whole sequence).
-
Split it between any two elements to get two new non-empty parts.
Each time after these steps you gain the number of points which is equal to product of sums of elements of each new part. You want to maximize the total number of points you gain.
Input Specification
The first line of the input file contains two integers $n$ and $k$ ($k + 1 \leq n$). The second line of input contains $n$ non-negative integers $a_1, a_2, \dotsc , a_ n (0 \leq a_ i \leq 10^4)$ – the sequence.
Output Specification
On the first line output the largest total number of points you can gain. On the second line output $k$ integers between $1$ and $n-1$ — the positions of elements after which you have to split the sequence to gain the largest total number of points. If there are more than one way to gain the largest number of points output any one of them.
Scoring
Your program will be tested on $6$ sets of input instances as follows:
Subtask 1 (points: 11)
$1 \leq k < n \leq 10$.
Subtask 2 (points: 11)
$1 \leq k < n \leq 50$.
Subtask 3 (points: 11)
$1 \leq k < n \leq 200$.
Subtask 4 (points: 17)
$2 \leq n \leq 1\, 000$, $1 \leq k \leq \min (n-1, 200)$.
Subtask 5 (points: 21)
$2 \leq n \leq 10\, 000$, $1 \leq k \leq \min (n-1, 200)$.
Subtask 6 (points: 29)
$2 \leq n \leq 100\, 000$, $1 \leq k \leq \min (n-1, 200)$.
Note
In the first sample you can gain $108$ points by the following way:
-
Initially you have the whole sequence $(4, 1, 3, 4, 0, 2, 3)$ as one part. You will split the sequence after 1st element and gain $4 \times (1 + 3 + 4 + 0 + 2 + 3) = 52$ points.
-
You have two parts $(4), (1, 3, 4, 0, 2, 3)$. You will split the sequence after 3rd element and gain $(1 + 3) \times (4 + 0 + 2 + 3) = 36$ points.
-
You have three parts $(4), (1, 3), (4, 0, 2, 3)$. You will split the sequence after 5th element and gain $(4 + 0) \times (2 + 3) = 20$ points.
So, after the steps taken above you get four parts $(4), (1, 3), (4, 0), (2, 3)$ and gain $52 + 36 + 20 = 108$ points.
| Sample Input 1 | Sample Output 1 |
|---|---|
7 3 4 1 3 4 0 2 3 |
108 1 3 5 |