苹果分堆

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

漂亮的老师给幼儿园的小宝宝们发 n 个苹果,每个苹果有一个新鲜度,老师先把苹果排成一排,然后在不打乱顺序的情况下将这排苹果分成若干堆(也就是要求分成的若干堆里面的苹果要是连续的),且每堆总些新鲜度不超过 k ,请问每一堆的总新鲜度最大值之和最小是多少(有可能答案不存在)
5 个苹果新鲜度分别为 5 6 7 3 9 ,若 k11 ,显然可以 5 6 为一堆, 7 3 为一堆, 9 为一堆,则答案是 6+7+9=2222 为最优答案

Input

第一行输入两个整数 nk
1<n,k<1e6
第二行输入 n 个整数,表示第 i 个苹果的新鲜度

Output

输出一个整数,表示答案
如果答案不存在,则输出 -1

Samples

5 10
2 6 5 8 4
23

3 2
4 5 6
-1

样例解释

对于样例一{(2,8)、(4,6)、(5)=8+6+5=19}更优但是分成的堆里面苹果不连续,所以不行 只能分成{(2,6)、(5)、(8)、(4)=6+5+8+4=23}

Limitation

1s, 1024KiB for each test case.

ACM21级内卷赛验题

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
18
Start at
2022-8-18 18:30
End at
2022-8-29 18:30
Duration
264 hour(s)
Host
Partic.
1