← 返回题目列表

Codeforces · 1431/F

F. 神经网络问题

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

您想要为毕业作品训练神经网络模型。数据集中有 $$$n$$$ 个图像,第 $$$i$$$ 个图像的大小为 $$$a_i$$$ 字节。

您没有任何强大的远程服务器来训练此模型,因此您必须在本地计算机上进行训练。但有一个问题:数据集的总大小对于您的机器来说太大了,因此您决定删除一些图像 - 尽管您不想使数据集太弱,因此您只能从中删除不超过 $$$k$$$ 图像。请注意,您只能删除图像,不能更改它们的顺序。

您希望以最佳方式删除这些图像,因此您想出了一个指标(毕竟您是数据科学家)来衡量删除结果。考虑删除最多 $$$k$$$ 图像后的数组 $$$b_1, b_2, \ldots, b_m$$$ ($$$n - k \le m \le n$$$)。该数组中的数据将以 $$$x$$$ 连续元素块的形式上传到机器。更准确地说:

- 索引从 $$$1$$$ 到 $$$x$$$ ($$$b_1, b_2, \ldots, b_x$$$) 的元素属于第一个块;
- 索引从 $$$x + 1$$$ 到 $$$2x$$$ ($$$b_{x + 1}, b_{x + 2}, \ldots, b_{2x}$$$) 的元素属于第二个块;
- 索引从 $$$2x + 1$$$ 到 $$$3x$$$ ($$$b_{2x + 1}, b_{2x + 2}, \ldots, b_{3x}$$$) 的元素属于第三个块;
- 等等。

总共会有 $$$cnt = \left\lceil\frac{m}{x}\right\rceil$$$ 块。请注意,如果 $$$m$$$ 不能被 $$$x$$$ 整除,则最后一个块包含的元素少于 $$$x$$$ ,这没问题。

设 $$$w(i)$$$ 为第 $$$i$$$ 块的总大小,即该块内图像大小的总和。例如,第一个块 $$$w(1)$$$ 的大小为 $$$b_1 + b_2 + \ldots + b_x$$$,第二个块 $$$w(2)$$$ 的大小为 $$$b_{x + 1} + b_{x + 2} + \ldots + b_{2x}$$$。

您提出的指标值是结果数据集块的最大块大小。换句话说,指标的值为 $$$\max\limits_{i=1}^{cnt} w(i)$$$。

您不想让机器过载太多,因此您必须以最小化上述指标值的方式删除最多 $$$k$$$ 个图像。

输入

输入的第一行包含三个整数 $$$n$$$、$$$k$$$ 和 $$$x$$$ ($$$1 \le n \le 10^5$$$; $$$1 \le k, x \le n$$$) — 分别是数据集中的图像数量、可以删除的最大图像数量以及每个块的长度(可能除了最后一个块)。

输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 图像的大小。

输出

打印一个整数:从数据集中删除不超过 $$$k$$$ 图像后问题陈述中描述的指标的最小可能值。

示例

输入 #1

5 5 4
1 1 5 4 5

输出 #1

0

输入 #2

5 2 4
6 1 5 5 6

输出 #2

11

输入 #3

6 1 4
3 3 1 3 1 2

输出 #3

8

输入#4

6 1 3
2 2 1 2 2 1

输出#4

5

注意

在第一个示例中,您可以删除整个数组,因此答案为 $$$0$$$。

在第二个示例中,可以删除 $$$a$$$ 的第一个和最后一个元素,得到 $$$b = [1, 5, 5]$$$。第一个(也是唯一的)块的大小是 $$$11$$$。所以答案是$$$11$$$。

在第三个示例中,删除$$$a$$$的第二个元素,得到$$$b = [3, 1, 3, 1, 2]$$$。第一个块的大小为 $$$8$$$,第二个块的大小为 $$$2$$$。所以答案是$$$8$$$。

在第四个例子中,可以保持数组$$$a$$$不变,得到$$$b = [2, 2, 1, 2, 2, 1]$$$。第一个块的大小为$$$5$$$,第二个块的大小也是如此。所以答案是$$$5$$$。