分数: 466 分
问题陈述
高桥正在尝试玩跳石游戏过河。
有 N 石头在河里排成一排,编号石头 1,石头 2,……,石头 N 从左到右。在石头上 i (1 \leq i \leq N),有 A_i 硬币已放置。
高桥最初站在石头上 1。当高桥站在一块石头上时,他会收集那块石头上的所有硬币(包括石头上的硬币) 1 他开始的地方)。他没有访问过的石头上的硬币无法收集。硬币数量不一定是正数;它可能是负数,在这种情况下,他也被迫收集它们。
虽然高桥还没有达到石头 N,他从当前的石头跳到右侧。当他现在在石头上时 i (i < N),他可以选择一个整数 d 与 1 \leq d \leq K 并移动到石头 i+d。但目标石子的数量最多为 N。也就是说,他可以跳到任何一块石头上 i+1,石头 i+2, \ldots,石头 \min(i+K,\, N)。由于运动总是向右,所以他不会两次站在同一块石头上。
高桥必须到达石头 N。当他到达石头时游戏结束 N 并收集其硬币。自从 K \geq 1 受限制,他总能到达石头 N 从石头上一步一步前进 1.
找出高桥从石头开始可以收集的最大硬币总数 1 并到达石头 N.
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N - 1
- -10^9 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 所有输入均为整数
输入
N K A_1 A_2 \ldots A_N
- 第一行包含一个整数 N 代表石子数量和一个整数 K 代表单次跳跃中可以覆盖的石头数量的最大差异,以空格分隔。
- 第二行包含整数 A_1, A_2, \ldots, A_N 代表每块石头上放置的硬币数量,以空格分隔。
输出
在一行中打印从石头移动时可以收集的最大硬币总数 1 去石头 N.