← 返回题目列表

AtCoder · awc0075_b

B. 水果丰收

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

分数: 333 分

问题陈述

高桥经营着一个果园。果园有 N 果树排成一排,编号 1, 2, \ldots, N 从左到右。

的 i第棵树熊 A_i 水果。

由于今年劳动力短缺,高桥无法砍伐所有树木,因此他决定精确选择 K 连续树木收获。具体来说,他选择一个整数 l (1 \leq l \leq N - K + 1)并从 K 树木已编号 l 通过 l + K - 1。他必须从每一个地方收获所有的果实。 K 选择了树(他不能部分收获一棵树),并且他不会从他没有选择的树上收获任何果实。

高桥希望尽量减少工作量,因此他希望尽量减少收获的水果总数。

找出当 K 连续的树被最优选择。

约束

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

输入

N K
A_1 A_2 \ldots A_N

第一行包含整数 N 表示果园中树木的数量和整数 K 代表要采伐的连续树木的数量,以空格分隔。

第二行包含整数 A_1, A_2, \ldots, A_N 代表每棵树上的水果数量,以空格分隔。

输出

在一行中打印出当 K 连续的树被最优选择。


示例输入 1

5 3
4 2 1 3 5

示例输出 1

6

示例输入 2

8 4
10 5 8 3 2 7 4 6

示例输出 2

16

示例输入 3

10 5
100 200 50 80 120 30 60 90 150 70

示例输出 3

340