← 返回题目列表

AtCoder · awc0072_b

B. 照料花坛

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

分数: 333 分

问题陈述

高桥管理 N 他的花园里排列着一排花坛。花坛都有编号 1 to N 从左到右,以及花坛 i 具有定义的“美丽”值 A_i.

对于每个 N 花坛,高桥选择是否维护它。但选择养护的花坛必须满足以下条件:

  • 存在一个整数 l (1 \leq l \leq N - K + 1) 使得花坛 l, l+1, \ldots, l+K-1 全部包含在维护的花坛中。

换句话说,必须存在至少一个区间,其中 K 连续的花坛全部维护完毕。只要满足这个条件,任何其他花坛都可以保留,也可以不保留。

找出选择用于维护的花坛的最大可能的美丽值总和。

约束

  • 1 \leq K \leq N \leq 5 \times 10^5
  • -10^9 \leq A_i \leq 10^9
  • 所有输入均为整数

输入

N K
A_1 A_2 \cdots A_N
  • 第一行包含花坛总数 N 以及必须维护的连续花坛数量 K,用空格分隔。
  • 第二行包含每个花坛的美丽值 A_1, A_2, \ldots, A_N,用空格分隔。

输出

在满足条件的情况下选择要维护的花坛时,将美丽值的最大总和打印在一行上。


示例输入 1

5 2
3 -5 4 2 -1

示例输出 1

9

示例输入 2

4 3
-2 -7 -1 -3

示例输出 2

-10

示例输入 3

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

示例输出 3

25

示例输入 4

20 6
4 -5 7 0 -2 9 -8 3 1 -4 6 -1 5 -7 2 8 -3 4 -6 10

示例输出 4

54

示例输入 5

1 1
-1000000000

示例输出 5

-1000000000