← 返回题目列表

AtCoder · awc0061_c

C. 果园收获

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

分数: 366 分

问题陈述

高桥参观了一个果园,那里 N 果树排成一排。树都被编号了 1, 2, \ldots, N 从一端开始,并且 i第树熊 A_i 水果。

高桥按照从树开始的顺序,一棵一棵地走过 1 到树 N。他从每棵树前面经过一次,就不能回头。当经过每棵树时,他选择收获 全部 那棵树上的果实或根本没有收获。他不能只收获一部分果实。也允许从任何树木上采摘。

然而,当他从树上采摘果实时,采摘带来的疲劳使他无法在下一次采摘 K 紧随其后的树木。也就是说,如果他从 i第棵树,他无法从树上收获 i+1 通过 i+K,他下一次收获最早是从树上 i+K+1 或更高版本。换句话说,如果他采伐的树木按编号升序排列,则任何两个相邻的编号 列表中的 i, j (i < j) 必须满足 j \geq i + K + 1。请注意,当 K = 0,此限制允许从连续的树上收获。

找出高桥可以收获的最大水果总数。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq K \leq N - 1
  • 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,用空格分隔。

输出

在一行中打印高桥可以收获的最大水果总数。


示例输入 1

5 2
3 7 2 5 8

示例输出 1

15

示例输入 2

8 1
10 20 30 40 50 60 70 80

示例输出 2

200

示例输入 3

15 3
100 50 30 20 200 10 5 150 80 40 300 25 15 60 250

示例输出 3

850