305943: CF1114B. Yet Another Array Partitioning Task
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
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