← 返回题目列表

AtCoder · soundhound2018_summer_final_b

B. 中和

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

配点 : 400 点

問題文

N 化学品水平排列。每种药物都有 整数值 効用 是固定的,从左边开始 i 药物目前的功效是 b_i 。这些值不一定是正值。

Kenkoooo 可以使用特殊的水平设备根据需要多次执行以下操作(尽管他不必这样做)。

  • 连续排队 选择 K 药物。所选药物的所有作用 0 变为。

请注意,移动化学品是危险的,不能这样做。

之后,Kenkoooo 喝掉所有 N 药物。在此之前,N 我想尽可能地最大化每种药物的效果总和。运算后求该和的最大值。

制約

  • 1 ≤ K ≤ N ≤ 2 × 10^5
  • -10^9 ≤ b_i ≤ 10^9
  • 所有输入值都是整数。

入力

输入是按以下格式从标准输入给出的。

N K
b_1
:
b_N

出力

操作后 输出 N 药物效果总和的最大值。


入力例 1

9 3
-1
-2
-3
4
5
-6
-7
-8
-9

出力例 1

9

以下是最佳过程的示例。

  • 1 第一个操作:从左开始 选择第 1, 2, 3 药物。
  • 2 第一个操作:从左开始 选择第 6, 7, 8 药物。
  • 3 第一个操作:从左开始 选择第 7, 8, 9 药物。

此时,9 每种药物的效果总和为 0 + 0 + 0 + 4 + 5 + 0 + 0 + 0 + 0 = 9 。 对于


入力例 2

5 4
-1
-1
5
-1
-1

出力例 2

1

你应该把药全部喝掉,什么也不做。


入力例 3

9 5
30
-20
40
60
-90
50
-40
10
70

出力例 3

120

入力例 4

10 1
1000000000
-1000000000
1000000000
-1000000000
1000000000
-1000000000
1000000000
-1000000000
1000000000
-1000000000

出力例 4

5000000000