#P13077. [NOISG 2019] Feast

    ID: 12877 Type: RemoteJudge 1000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>2019NOISG(新加坡)

[NOISG 2019] Feast

题目描述

Gug 正在为他的朋友们准备一场盛宴。盛宴由 NN 盘食物组成,按顺序排列,第 ii 盘食物若被食用,可带来 AiA_i 点满足感。部分食物可能已经腐烂,因此 AiA_i 可能为负数。

共有 KK 个人参加盛宴,每人将被分配一段连续的食物区间食用。该区间可以为空,且不同人的区间不得重叠,每盘食物最多只能被食用一次。

Gug 希望合理分配食物,使得所有被食用的食物带来的满足感总和最大。

请你计算,最大满足感总和是多少。

输入格式

第一行包含两个整数 NNKK

第二行包含 NN 个整数 A1,A2,,ANA_1, A_2, \dots, A_N

输出格式

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

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:

将唯一一人分配到区间 [3,1,5][3,-1,5],满足感总和为 77

对于样例 2:

选择连续区间 [1,2,3][1,2,3][5,6][5,6],总和最大。

对于样例 3:

所有满足感均不为正,最优选择是所有人都选择空区间,总和为 00

【数据范围】

  • 1KN3×1051 \leq K \leq N \leq 3 \times 10^5
  • 0Ai1090 \leq |A_i| \leq 10^9
子任务编号 分值 额外限制
11 44 Ai0A_i \geq 0
22 88 至多有一个位置 Ai<0A_i < 0
33 1818 K=1K = 1
44 1010 1KN801 \leq K \leq N \leq 80
55 1111 1KN3001 \leq K \leq N \leq 300
66 2020 1KN20001 \leq K \leq N \leq 2000
77 2929 无额外限制