5106. 佩奇的小飞机

单点时限: 1.0 sec

内存限制: 128 MB

佩奇开着她自制的迷你小飞机来参加一个游戏。这个游戏中有一块 $1\times N$ 大小的铺着瓷砖的区域,这个区域由 $N$ 块 $1\times 1$ 大小的正方形瓷砖从左到右依次拼接而成。其中,每块瓷砖中心的正上方1m处都有一个小礼品,每个礼品都有一个价值。

如下图所示,佩奇开着她的小飞机从左边第 $1$ 块瓷砖的中心点向右出发,最后必须停止在右边第 $1$ 块瓷砖的中心点。由于她自己造的迷你小飞机还在初步研发阶段,功能十分有限,只有起飞、平行于地面飞行、降落这 $3$ 个功能。每个功能详细情况如下:

  1. 起飞时,只能向图片中的右上方飞行,仰角固定为 45°,飞行目标高度固定为1m;
  2. 平行于地面飞行时,只能往图片正右方飞行,飞行高度固定为$1$ ,每次起飞后平行飞行的距离不超过 $K$(平行飞行阶段的飞行距离是一个不超过 $K$ 的非负整数,每次降落又重新起飞后,平行飞行距离重新计数);
  3. 降落时,只能向图片中的右下方飞行,俯角固定为 45°,降落目标为右下方瓷砖的中心点,降落高度固定为 $1$。

当佩奇在飞行过程中经过某些礼品时,她就能拿到这些礼品。佩奇想要知道她能获得的礼品价值总和最大是多少

备注:上图为样例 #1 对应的图例, $K=3$ 时,飞机每次起飞后佩奇可以拿到最多 $K+1=4$ 个小礼品。经过 $3$ 次起飞与降落,佩奇最多能获得价值 $7+3+9+8+10+6+9+11=63$ 的礼品。注意,佩奇的小飞机在地面上不能滑行或移动,只能在每块瓷砖的中心点停歇。

输入格式

输入共 $2$ 行。第一行包含两个整数 $N(3\leq N\leq 10^6)$ 和 $K(1\leq K \leq N)$ ,分别表示瓷砖的数量和小飞机平行飞行阶段的最大飞行距离。第二行包含 $N$ 个由空格隔开的正整数,从左到右分别为 $A_1, A_2,\cdots, A_N(1\leq A_1,A_2,\cdots,A_N\leq 10^9)$,表示图中从左到右第 $1$ 块瓷砖到第 $N$ 块瓷砖上方的礼品价值。

输出格式

输出一个值,表示佩奇能获得的礼品价值总和最大值。

样例

Input
12 3
79 7 1 3 9 8 10 7 6 9 11 8
Output
63
Input
8 1
3 9 9 1 1 9 9 26
Output
28

41 人解决,62 人已尝试。

51 份提交通过,共有 275 份提交。

4.9 EMB 奖励。

创建: 9 月,3 周前.

修改: 9 月,2 周前.

最后提交: 7 月前.

来源: N/A

题目标签