← 返回题目列表

Codeforces · 1114/B

B. 又一个数组分区任务

中文机器翻译题面 查看原题

一个数组 $$$b$$$ 被称为 $$$a$$$ 的子数组,如果它形成 $$$a$$$ 的连续子序列,也就是说,如果它对于某些 $$$l 等于 $$$a_l$$$、$$$a_{l + 1}$$$、$$$\ldots$$$、$$$a_r$$$, r$$$。

假设 $$$m$$$ 是某个已知常数。对于任何具有 $$$m$$$ 或更多元素的数组,我们将其美丽定义为该数组的 $$$m$$$ 最大元素的总和。例如:

- 对于数组$$$x = [4, 3, 1, 5, 2]$$$和$$$m = 3$$$,$$$x$$$的$$$3$$$最大元素是$$$5$$$、$$$4$$$和$$$3$$$,所以$$$x$$$的美丽是$$$5 + 4 + 3 = 12$$$。
- 对于数组 $$$x = [10, 10, 10]$$$ 和 $$$m = 2$$$,$$$x$$$ 的美妙之处在于 $$$10 + 10 = 20$$$。

给定一个数组 $$$a_1, a_2, \ldots, a_n$$$,所述常量的值 $$$m$$$ 和一个整数 $$$k$$$。您需要将数组 $$$a$$$ 精确地拆分为 $$$k$$$ 子数组,以便:

- $$$a$$$ 中的每个元素都属于一个子数组。
- 每个子数组至少有 $$$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$$$ 中的元素数量, beauty 定义中的常量 $$$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$$$ 子数组。

如果有多个最佳分区,则打印其中任何一个。

示例

输入 #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

注意

在第一个示例中,最佳分区之一是 $$$[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]$$$。