← 返回题目列表

AtCoder · awc0012_e

E. 石头穿越游戏

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

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