← 返回题目列表

AtCoder · jsc2023_final_a

A. 苹果瘾

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

配点 : 300 点

問題文

1 从 N 有 N 苹果。 苹果 i 的美味 A_i 。 A_i 也可能为负。 另外,整数 给出了 K 。

您可以多次执行以下操作( 它可以重复(甚至0 次)。

  • 整数 i (1 \leq i \leq N-K+1)并选择苹果 吃 i,i+1,\cdots,i+K-1 。 请注意,对于之前操作中已经吃掉的苹果,不会执行任何操作。

最后,找出你吃的苹果的美味程度的最大可能总和。

制約

  • 1 \leq K \leq N \leq 250000
  • -10^9 \leq A_i \leq 10^9
  • 所有输入值都是整数。

入力

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

N K
A_1 A_2 \cdots A_N

出力

打印答案。


入力例 1

4 2
2 -1 2 -2

出力例 1

3

可以进行以下操作。 选择

  • i=1 和苹果 吃 1,2 。 吃
  • i=2 和苹果 吃 3 。 (苹果 2 已经被吃掉了,所以什么也不做)

此时吃到的苹果总的好吃度是 它变成 A_1+A_2+A_3=3 。 无论你如何操纵它,你吃的苹果的总美味将是 它不会超过 3 。 因此答案是 3 。


入力例 2

5 5
3 1 4 1 5

出力例 2

14

入力例 3

5 1
-1 -2 -3 -4 -5

出力例 3

0

入力例 4

20 4
573641910 -499039319 421342458 893335602 -961457884 -190195710 -497364364 -954575123 41286305 -310659388 -451608793 122064200 -719921087 87712135 43831420 714154567 -451280 -161259952 488561040 -501663741

出力例 4

2561828581