配点: 100 点
問題文
在桌子上 N 糖果从左侧开始水平排列。 它们的编号最大为 1 从 N 。糖果 i (1 \leqq i \leqq N) 的美味是 A_i 。
嗨你, 我决定选择一些N 糖果并吃掉它们。
不过,为了避免吃太多糖果, 至于 K 块糖果,最多 尝试只吃 2 块。也就是说,哪个 j (1 \leqq j \leqq N - K + 1)还有糖果。 j 卡拉糖果 连续直至 j + K - 1 连续到 K 吃掉的糖果数量为 必须小于或等于 2 。
在这种情况下,JOI 希望最大化他吃的糖果的总美味。
N 单个糖果的美味 给定 K ,编写一个程序,找出 JOI 吃的糖果的美味度总和的最大值。
制約
- 2 \leqq K \leqq N \leqq 3\,000.
- 1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N).
- 所有输入值都是整数。
小課題
- (4 点) N \leqq 20.
- (19 点) K \leqq 10.
- (47 点) N \leqq 300.
- (30 点)没有额外的限制。
评分注意事项
所有提交的内容都将通过评审系统进行评分。
如果提交的源代码为与该子作业对应的所有评分输入数据返回正确的结果,则该源代码将被识别为该子作业的正确结果。
每次提交的分数是所提交源代码被认为正确的子任务分数的总和。
该作业的分数是此作业所有提交的最高分。
您可以在“提交结果”选项卡上的“我的分数状态”中查看您当前的分数。
入力
输入是按以下格式从标准输入给出的。
N K A_1 A_2 \cdots A_N
出力
JOI吃的糖果的总美味度最大值输出到标准输出。 1 行。
入力例 1
5 4 1 3 2 4 3
出力例 1
8
JOI君雨 吃 1 ,飴 4 , 飴 5 时,总美味为 8 变为。
哪个连续 4 吃掉的糖果数量是 2 小于1的吃法中,总的美味是 由于不存在大于或等于 9 的东西, 8 。 如果发现
此输入示例满足所有子任务约束。
入力例 2
6 3 3 7 1 5 6 4
出力例 2
21
JOI君雨 吃 1 ,飴 2 , 飴 4 ,飴 5 时,总美味为 21 变为。
哪个连续 3 吃掉的糖果数量是 2 小于1的吃法中,总的美味是 由于不存在大于或等于 22 的东西, 21 。 如果发现
此输入示例满足所有子任务约束。
入力例 3
5 2 3 3 2 2 1
出力例 3
11
此输入示例满足所有子任务约束。
入力例 4
12 5 864814169 716638377 926889183 891468826 217138351 891972397 504371916 678159995 435478604 181254225 760822841 688502728
出力例 4
4427122428
此输入示例满足所有子任务约束。