TDOG模拟 #3 花环

TDOG模拟 #3 花环

花环(garland)

题目描述

Kiana有一个漂亮的花环,花环上有nn朵五颜六色的花儿,这些花儿构成了一个环形的结构,沿顺时针方向依次编号为1,2,,n1,2,\cdots,n,且第nn朵花儿与第11朵花儿也是相邻的。

Kiana的小伙伴们都喜欢花儿,于是Kiana决定献出自己的花环,把花儿分给自己的朋友。具体而言,Kiana共有mm个小伙伴,故她希望在花环上剪下mm段连续的区间来,每个区间可以包含任意多朵花儿,但每朵花儿至多属于一个区间。

当然,并非每朵花儿都讨Kiana喜爱,于是她给了每朵花儿一个魅力值,其中有些好看的花儿魅力值就为正数,有些Kiana觉得不好看的花儿魅力值就为负数。

Kiana希望自己剪下来送给小伙伴的花儿的魅力值总和尽可能大,并想求出这个最大值是多少。由于Kiana自己不会算,所以希望你能够帮助她。

输入输出格式

输入格式

第一行包含两个正整数nnmm,分别表示花环上花儿的数量与Kiana的小伙伴数量。

第二行包含nn个整数,其中第ii个整数FiF_i表示第ii朵花儿的魅力值。数据保证至少有mm朵花儿的魅力值是正数,即Kiana最后得到的魅力值总和总是可以大于00的。

输出格式

输出一行一个正整数,表示Kiana能够剪下来的花儿的最大魅力值总和。

输入输出样例

输入样例#1:

10 3
-1 6 -2 7 -3 8 -4 9 -5 10 

输出样例#1:

37

输入样例#2:

garland2.in

输出样例#2:

garland2.ans

输入样例#3:

garland3.in

输出样例#3:

garland3.ans

输入样例#4:

garland4.in

输出样例#4:

garland4.ans

输入样例#5:

garland5.in

输出样例#5:

garland5.ans

样例解释

Kiana的花环上共有1010朵花儿,其魅力值依次为1,6,2,7,3,8,4,9,5,10-1,6,-2,7,-3,8,-4,9,-5,10,Kiana需要从中选出33个区间来送给自己的小伙伴。那么,Kiana会选择第10,1,2,3,410,1,2,3,4朵花构成的区间和第66朵、第88朵花单独构成的两个区间,第11个区间的魅力值为10+(1)+6+(2)+7=2010+(-1)+6+(-2)+7=20,后两个区间的魅力值分别为8899,故总的魅力值为20+8+9=3720+8+9=37,可以证明这是魅力值最大的选择方案。

数据范围

对于25%25\%的数据,保证1n30,1m101\leq n\leq 30,1\leq m\leq 10

对于50%50\%的数据,保证1n3000,1m10001\leq n\leq 3000,1\leq m\leq 1000

对于100%100\%的数据,保证1n3×105,1m105,100Fi1001\leq n\leq 3\times 10^5,1\leq m\leq 10^5,-100\leq F_i\leq 100Fi0F_i\neq 0

上面每一档数据内部,各有20%20\%的数据保证m=1m=1,还有20%20\%的数据保证m=2m=2,另有20%20\%的数据保证m10m\leq 10

信息

ID
1016
难度
9
分类
(无)
标签
递交数
7
已通过
3
通过率
43%
上传者