4311. 「ROIR 2022 Day2」礼物

传统 $1000$ ms $512$ MiB
$7$ 通过 $19$ 提交

题目描述

译自 ROI Regional 2022 Day2 T4. Подарки

圣诞老人让沃瓦选择新年礼物。

沃瓦面前有一排 $n$ 个礼物。每个礼物都有一个整数值，第 $i$ 个礼物的值为 $a_i$，表示这个礼物能给沃瓦带来的快乐值。快乐值可以是正数、负数或零。

圣诞老人让沃瓦选择两个数 $l$ 和 $r$，满足 $1 \le l \le r \le n$，并拿走从第 $l$ 个到第 $r$ 个的所有礼物。然而，沃瓦必须将选中的礼物中快乐值最大的 $k$ 个礼物送给他的妹妹玛莎，剩下的礼物沃瓦自己留下。

沃瓦希望选择 $l$ 和 $r$，使得他自己得到的礼物的总快乐值最大。礼物的总快乐值是这些礼物的 $a_i$ 值的总和。

请帮助沃瓦选择 $l$ 和 $r$，使得 $1 \le l \le r \le n$，$r - l + 1 \ge k$，并且沃瓦自己得到的礼物的总快乐值最大。

输入格式

第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^5$，$0 \le k \le \min(100, n)$），表示沃瓦面前的礼物数量和需要送给玛莎的礼物数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \le a_i \le 10^9$），表示每个礼物的快乐值。

输出格式

输出一个整数，表示沃瓦自己得到的礼物的总快乐值。

样例 1

输入

5 0
2 -4 5 -1 7

输出

11

说明

在样例 1 中，沃瓦不需要给玛莎任何礼物，所以他会选择 $l = 3$，$r = 5$，他得到的礼物的总快乐值为 $5 + (-1) + 7 = 11$。

样例 2

输入

5 1
2 -4 5 -1 7

输出

4

说明

在样例 2 中，沃瓦需要给玛莎一个快乐值最大的礼物。他仍然会选择 $l = 3$，$r = 5$，但他得到的礼物的总快乐值为 $5 + (-1) = 4$。

样例 3

输入

5 2
2 -4 5 -1 7

输出

0

说明

在样例 3 中，沃瓦需要给玛莎两个快乐值最大的礼物。在这种情况下，最优选择是 $l = 1$，$r = 2$。

数据范围与提示

详细子任务附加限制及分值如下表所示：

子任务	分值	附加限制	子任务依赖
$1$	$7$	$n \le 200$	无
$2$	$8$	$n \le 1000$	$1$
$3$	$10$	$n \le 6000$	$1, 2$
$4$	$8$	$k = 0$	无
$5$	$14$	$k = 1$
$6$	$39$	$n \le 80000$	$1 \sim 3$
$7$	$14$	无	$1 \sim 6$