CF1114B Yet Another Array Partitioning Task

如果一个数组 $b$ 是数组 $a$ 的一个子数组，那么它一定是 $a$ 的一个连续子序列，即存在某些 $l, r$ 使得 $b = a_l, a_{l+1}, \ldots, a_r$。 假设 $m$ 是一个已知常数。对于任意长度不少于 $m$ 的数组，我们定义它的“美丽值”为该数组中最大的 $m$ 个元素之和。例如： - 对于数组 $x = [4, 3, 1, 5, 2]$ 且 $m = 3$，最大的 $3$ 个元素为 $5, 4, 3$，所以 $x$ 的美丽值为 $5 + 4 + 3 = 12$。 - 对于数组 $x = [10, 10, 10]$ 且 $m = 2$，美丽值为 $10 + 10 = 20$。 现在给定一个数组 $a_1, a_2, \ldots, a_n$，已知常数 $m$ 和整数 $k$。你需要将数组 $a$ 划分为恰好 $k$ 个子数组，要求： - 每个元素都属于且只属于一个子数组。 - 每个子数组的长度不少于 $m$。 - $k$ 个子数组的美丽值之和最大。

第一行包含三个整数 $n, m, k$（$2 \le n \le 2 \cdot 10^5$，$1 \le m$，$2 \le k$，$m \cdot k \le n$）——表示数组 $a$ 的长度、美丽值定义中的常数 $m$ 以及要划分的子数组个数。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \le a_i \le 10^9$）。

第一行输出在最优划分下，所有子数组美丽值之和的最大值。 第二行输出 $k-1$ 个整数 $p_1, p_2, \ldots, p_{k-1}$（$1 \le p_1 < p_2 < \ldots < p_{k-1} < n$），表示数组的划分方式： - 下标 $1$ 到 $p_1$ 的元素属于第一个子数组。 - 下标 $p_1+1$ 到 $p_2$ 的元素属于第二个子数组。 - $\ldots$ - 下标 $p_{k-1}+1$ 到 $n$ 的元素属于第 $k$ 个子数组。 如果有多种最优划分方案，输出任意一种即可。

在第一个样例中，一种最优划分为 $[5, 2, 5]$，$[2, 4]$，$[1, 1, 3, 2]$。 - 子数组 $[5, 2, 5]$ 的美丽值为 $5 + 5 = 10$。 - 子数组 $[2, 4]$ 的美丽值为 $2 + 4 = 6$。 - 子数组 $[1, 1, 3, 2]$ 的美丽值为 $3 + 2 = 5$。 它们的美丽值之和为 $10 + 6 + 5 = 21$。 在第二个样例中，一种最优划分为 $[4]$，$[1, 3]$，$[2, 2]$，$[3]$。 由 ChatGPT 4.1 翻译