P13077 [NOISG 2019] Feast

Gug 正在为他的朋友们准备一场盛宴。盛宴由 $N$ 盘食物组成，按顺序排列，第 $i$ 盘食物若被食用，可带来 $A_i$ 点满足感。部分食物可能已经腐烂，因此 $A_i$ 可能为负数。 共有 $K$ 个人参加盛宴，每人将被分配一段连续的食物区间食用。该区间可以为空，且不同人的区间不得重叠，每盘食物最多只能被食用一次。 Gug 希望合理分配食物，使得所有被食用的食物带来的满足感总和最大。 请你计算，最大满足感总和是多少。

第一行包含两个整数 $N$ 和 $K$。 第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$。

输出一个整数，表示最大满足感总和。

【样例解释】 对于样例 1： 将唯一一人分配到区间 $[3,-1,5]$，满足感总和为 $7$。 对于样例 2： 选择连续区间 $[1,2,3]$ 和 $[5,6]$，总和最大。 对于样例 3： 所有满足感均不为正，最优选择是所有人都选择空区间，总和为 $0$。 【数据范围】 - $1 \leq K \leq N \leq 3 \times 10^5$ - $0 \leq |A_i| \leq 10^9$ | 子任务编号 | 分值 | 额外限制 | | :---: | :---: | :---: | | $1$ | $4$ | $A_i \geq 0$ | | $2$ | $8$ | 至多有一个位置 $A_i < 0$ | | $3$ | $18$ | $K = 1$ | | $4$ | $10$ | $1 \leq K \leq N \leq 80$ | | $5$ | $11$ | $1 \leq K \leq N \leq 300$ | | $6$ | $20$ | $1 \leq K \leq N \leq 2000$ | | $7$ | $29$ | 无额外限制 |