← 返回题目列表

AtCoder · agc008_b

B. 连续重新绘制

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

分数: 400 点

问题陈述

有 N 方块排成一行。 的 i从左边算起第一个方格包含一个整数 a_i.

最初,所有方块都是白色的。 Snuke 会多次执行以下操作:

  • 选择 K 连续的方块。然后,将它们全部漆成白色,或全部漆成黑色。在这里,方块的颜色被覆盖。

Snuke执行完操作后,分数将计算为黑色方块中包含的整数之和。 找出可能的最高分数。

约束

  • 1≤N≤10^5
  • 1≤K≤N
  • a_i 是一个整数。
  • |a_i|≤10^9

输入

输入由标准输入按以下格式给出:

N K
a_1 a_2 ... a_N

输出

打印可能的最大分数。


示例输入 1

5 3
-10 10 -10 10 -10

示例输出 1

10

将以下方块涂成黑色:左起第二个、第三个和第四个方块。


示例输入 2

4 2
10 -10 -10 10

示例输出 2

20

获得最高分数的一种可能方法如下:

  • 将以下方块涂成黑色:从左边算起的第一个和第二个方块。
  • 将以下方块涂成黑色:左起第三个和第四个方块。
  • 将以下方块涂成白色:左起第二个和第三个方块。

示例输入 3

1 1
-10

示例输出 3

0

示例输入 4

10 5
5 -4 -5 -8 -4 7 2 -4 0 7

示例输出 4

17