Codeforces Round 538 (Div. 2) |
---|
Finished |
An array $$$b$$$ is called to be a subarray of $$$a$$$ if it forms a continuous subsequence of $$$a$$$, that is, if it is equal to $$$a_l$$$, $$$a_{l + 1}$$$, $$$\ldots$$$, $$$a_r$$$ for some $$$l, r$$$.
Suppose $$$m$$$ is some known constant. For any array, having $$$m$$$ or more elements, let's define it's beauty as the sum of $$$m$$$ largest elements of that array. For example:
You are given an array $$$a_1, a_2, \ldots, a_n$$$, the value of the said constant $$$m$$$ and an integer $$$k$$$. Your need to split the array $$$a$$$ into exactly $$$k$$$ subarrays such that:
The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m$$$, $$$2 \le k$$$, $$$m \cdot k \le n$$$) — the number of elements in $$$a$$$, the constant $$$m$$$ in the definition of beauty and the number of subarrays to split to.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$).
In the first line, print the maximum possible sum of the beauties of the subarrays in the optimal partition.
In the second line, print $$$k-1$$$ integers $$$p_1, p_2, \ldots, p_{k-1}$$$ ($$$1 \le p_1 < p_2 < \ldots < p_{k-1} < n$$$) representing the partition of the array, in which:
If there are several optimal partitions, print any of them.
9 2 3 5 2 5 2 4 1 1 3 2
21 3 5
6 1 4 4 1 3 2 2 3
12 1 3 5
2 1 2 -1000000000 1000000000
0 1
In the first example, one of the optimal partitions is $$$[5, 2, 5]$$$, $$$[2, 4]$$$, $$$[1, 1, 3, 2]$$$.
The sum of their beauties is $$$10 + 6 + 5 = 21$$$.
In the second example, one optimal partition is $$$[4]$$$, $$$[1, 3]$$$, $$$[2, 2]$$$, $$$[3]$$$.
Name |
---|