← 返回题目列表

AtCoder · awc0058_b

B. 苹果丰收

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

分数: 333 分

问题陈述

高桥经营着一个果园。果园有 N 苹果树排成一排,编号树 1,树 2, \ldots,树 N 从左到右。树 i 有 H_i 苹果生长在上面。

为了简化收获过程,高桥将选择一对整数 (L, R) (1 \leq L \leq R \leq N) 代表一系列连续的树编号,并从树上的所有树上收获苹果 L 到树 R。然而,由于工人数量有限,范围内的树木数量, R - L + 1,最多必须是 M,其中 M 是单次采伐操作中可以处理的最大树木数量。

收获的苹果中,只有符合运输标准的树上的苹果才能运往市场。具体来说,对于树 i 来自树 L 到树 R,只有树上的苹果满足 H_i \geq K 符合发货条件。从每棵符合条件的树中,所有 H_i 那棵树上生长的苹果已发货。可运送的苹果总数为 H_i 所有符合条件的树木。如果范围内没有符合运输标准的树,则可运输的苹果总数为 0.

求高桥选择时可以运送的最大苹果总数 (L, R) 最佳。

约束

  • 1 \leq N \leq 10^6
  • 1 \leq M \leq N
  • 1 \leq K \leq 10^9
  • 0 \leq H_i \leq 10^9
  • 所有输入值均为整数

输入

N M K
H_1 H_2 \ldots H_N
  • 第一行包含整数 N 代表树的数量,整数 M 表示单次采伐操作中可以处理的最大树木数量,整数 K 代表满足运输标准所需的最少苹果数量,以空格分隔。
  • 第二行包含整数 H_1, H_2, \ldots, H_N 代表每棵树上生长的苹果数量,以空格分隔。

输出

在一行上打印可以运送的苹果的最大总数。


示例输入 1

5 3 5
3 7 2 8 6

示例输出 1

15

示例输入 2

4 2 10
3 5 2 1

示例输出 2

0

示例输入 3

10 4 3
1 5 0 4 7 2 9 3 1 6

示例输出 3

20

示例输入 4

20 6 5
2 8 1 10 3 7 0 15 6 4 12 5 9 2 11 3 8 1 7 6

示例输出 4

47

示例输入 5

1 1 1
1000000000

示例输出 5

1000000000