苹果分堆
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 ，若 k 取 11 ，显然可以 5 6 为一堆， 7 3 为一堆， 9 为一堆，则答案是 6+7+9=22 且 22 为最优答案
Input
第一行输入两个整数 n 和 k
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.
第六届SWPU-ACM正式队员选拔赛
- Status
- Done
- Rule
- ACM/ICPC
- Problem
- 18
- Start at
- 2022-8-28 14:00
- End at
- 2022-8-28 19:00
- Duration
- 5 hour(s)
- Host
-
mibbp
- Partic.
- 35