AT_joi2022_yo2_d.飴 2 (Candies 2)

题目简述

有一个长为 $N$ 的数列 $A$。现要从 $A$ 中选出若干数，但任意连续的 $K$ 个整数中最多只许选两个。请求出选出的数的和的最大值。

第一行输入两个整数 $N,K$。

第二行输入 $N$ 个整数，表示数列 $A$。

一行一个整数，表示和的最大值。

样例 #1 解释

选择第 $1,4,5$ 个数，和为 $8$。

该样例满足所有子任务。

样例 #2 解释

选择第 $1,2,4,5$ 个数，和为 $21$。

该样例满足全部子任务。

样例 #3 解释

该样例满足所有子任务。

样例 #4 解释

该样例满足全部子任务。

数据规模与约定

对于全部测试点，数据保证：

• $2\le K\le N\le 3000$；
• $1\le A_i\le 10^9$（$1\le i\le N$）。

本题采用捆绑测试。 各子任务分值及特殊限制见下表：

子任务编号	分值	特殊限制
$1$	$4$	$N\le 20$
$2$	$19$	$K\le 10$
$3$	$47$	$N\le 300$
$4$	$30$	无特殊限制