Yet Another Array Partitioning Task
Contest: Codeforces Round 538 (Div. 2)
Difficulty rating: 1500
Tags: constructive algorithms, greedy, sortings

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:

- For array $$$x = [4, 3, 1, 5, 2]$$$ and $$$m = 3$$$, the $$$3$$$ largest elements of $$$x$$$ are $$$5$$$, $$$4$$$ and $$$3$$$, so the beauty of $$$x$$$ is $$$5 + 4 + 3 = 12$$$.
- For array $$$x = [10, 10, 10]$$$ and $$$m = 2$$$, the beauty of $$$x$$$ is $$$10 + 10 = 20$$$.

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:

- Each element from $$$a$$$ belongs to exactly one subarray.
- Each subarray has at least $$$m$$$ elements.
- The sum of all beauties of $$$k$$$ subarrays is maximum possible.

Input format:
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$$$).

Output format:
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:

- All elements with indices from $$$1$$$ to $$$p_1$$$ belong to the first subarray.
- All elements with indices from $$$p_1 + 1$$$ to $$$p_2$$$ belong to the second subarray.
- $$$\ldots$$$.
- All elements with indices from $$$p_{k-1} + 1$$$ to $$$n$$$ belong to the last, $$$k$$$-th subarray.

If there are several optimal partitions, print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, one of the optimal partitions is $$$[5, 2, 5]$$$, $$$[2, 4]$$$, $$$[1, 1, 3, 2]$$$.

- The beauty of the subarray $$$[5, 2, 5]$$$ is $$$5 + 5 = 10$$$.
- The beauty of the subarray $$$[2, 4]$$$ is $$$2 + 4 = 6$$$.
- The beauty of the subarray $$$[1, 1, 3, 2]$$$ is $$$3 + 2 = 5$$$.

The sum of their beauties is $$$10 + 6 + 5 = 21$$$.

In the second example, one optimal partition is $$$[4]$$$, $$$[1, 3]$$$, $$$[2, 2]$$$, $$$[3]$$$.

Example input:
9 2 3
5 2 5 2 4 1 1 3 2

Example output:
21
3 5

Example input:
6 1 4
4 1 3 2 2 3

Example output:
12
1 3 5

Editorial:
In a perfect scenario, the maximum beauty of the original array is just a sum of $$$m \cdot k$$$ largest elements.
In fact, such scenario is always available regardless of the elements.
Let's denote $$$A$$$ as the set of these $$$m \cdot k$$$ largest elements. The solution for us will be dividing the array into $$$k$$$ segments, such that each segment contains exactly $$$m$$$ elements of $$$A$$$. Just make a split between corresponding elements in the set $$$A$$$.
Depending on the way we find $$$m \cdot k$$$ largest elements, the time complexity might differ.
If we simply do so after sorting the entire array by usual means, the time complexity will be $$$\mathcal{O} \left( n \cdot \log(n) \right)$$$.
However, we can use std::nth_element function instead of sorting the entire array. The idea is to sort the array in such a way that, every elements not higher than a value $$$v$$$ will be stored in the left side, other elements will stay on the right, and this works in linear time (a.k.a. $$$\mathcal{O} \left( n \right)$$$ time complexity).
An example implementation of such ordering can be shown here.
Thanks kun and neko_nyaa for showing me this.