分数: 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