Yet Another Array Partitioning Task

题意翻译

定义一个序列的“美丽度”为这个序列前 $m$ 大的数的和。现在有一个长度为 $n$ 的序列,你需要把它分成 $k$ 个长度至少为 $m$ 的连续子序列,每个元素不重不漏,使得这些子串的“美丽度”之和最大。而且要求输出划分方案。 $1\le n\le 2\times 10^5,m\ge 1,k\ge 2,m\times k\le n$。

题目描述

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.

输入输出格式

输入格式


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: - 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.

输入输出样例

输入样例 #1

9 2 3
5 2 5 2 4 1 1 3 2

输出样例 #1

21
3 5 

输入样例 #2

6 1 4
4 1 3 2 2 3

输出样例 #2

12
1 3 5 

输入样例 #3

2 1 2
-1000000000 1000000000

输出样例 #3

0
1 

说明

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] $ .