← 返回题目列表

AtCoder · code_festival_2015_okinawa_j

J. 丛林

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

问题

沃尔夫·索斯在丛林中拥有一大片土地。在这片线性土地上, N 树木定期生长。尺寸 i_{th} 树从一端给出为 t_i.

丛林内部一片漆黑,因为树木阻挡了阳光。为了让阳光照进丛林, 沃尔夫·索特考虑削减一些 N 树木(或不砍伐任何人)。更具体地说,树木将按照以下规则砍伐。

  • 最多 M 树木可以砍伐(不超过 M).
  • 考虑到对周围生态系统的影响,不允许任意砍伐两棵或两棵以上树木 K 连续的树。更准确地说,不存在 i(1≦i≦N-K+1) 这样 2 或更多树木被砍伐 i_{th}, (i + 1)_{th}, ......, (i + K-1)_{th} 树从一端开始。
  • 如果沃尔夫·索斯削减 i_{th} 树从一端开始,树的大小 t_i 变为 0.
  • 我们想要大小总和的最大值 K 连续的树要尽可能小。也就是说,我们想要最小化 .

由于尺寸 N 树木和 M, K 已给出,当我们对树木进行最优砍伐选择时,请求出连续树木尺寸总和的最大值中的最小值 K 树。


输入

输入将通过以下格式的标准输入给出。

N M K
t_1
t_2
:
t_N
  • 第一行,整数 将给出 N(1≦N≦100,000), M(1≦M≦N), K(1≦K≦N) 。
  • 从第二行开始有 N 附加行提供有关树木大小的信息。 i_{th} 行,整数 t_i(1≦t_i≦1,000,000,000) 。

输出

请打印连续尺寸总和的最大值与最小值 K 树木,当我们为一行中的树木做出最佳切割选择时。

在输出末尾打印换行符。


输入示例 1

6 2 3
1
5
6
2
4
3

输出示例 1

7

如果沃尔夫·索斯削减 3_{rd} 和 6_{th} 树,连续的大小总和的最小值与最大值 3 当为 2_{nd}, 3_{rd}, 4_{th} 树。大小的总和是 5+0+2=7.


输入示例 2

10 3 4
3
14
1
5
9
2
6
5
3
5

输出示例 2

17