#P13077. [NOISG 2019] Feast
[NOISG 2019] Feast
题目描述
Gug 正在为他的朋友们准备一场盛宴。盛宴由 盘食物组成,按顺序排列,第 盘食物若被食用,可带来 点满足感。部分食物可能已经腐烂,因此 可能为负数。
共有 个人参加盛宴,每人将被分配一段连续的食物区间食用。该区间可以为空,且不同人的区间不得重叠,每盘食物最多只能被食用一次。
Gug 希望合理分配食物,使得所有被食用的食物带来的满足感总和最大。
请你计算,最大满足感总和是多少。
输入格式
第一行包含两个整数 和 。
第二行包含 个整数 。
输出格式
输出一个整数,表示最大满足感总和。
6 1
1 -2 3 -1 5 -6
7
6 2
1 2 3 -10 5 6
17
6 4
-1 -2 -1 0 -5 -1
0
提示
【样例解释】
对于样例 1:
将唯一一人分配到区间 ,满足感总和为 。
对于样例 2:
选择连续区间 和 ,总和最大。
对于样例 3:
所有满足感均不为正,最优选择是所有人都选择空区间,总和为 。
【数据范围】
子任务编号 | 分值 | 额外限制 |
---|---|---|
至多有一个位置 | ||
无额外限制 |