#BZOJ2862. 分糖果
-
ID: 1341
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
root
分糖果
No submission language available for this problem.
题目描述
小W有N颗糖果，去助学的时候，小W希望将这N颗糖果分给所在的k个小朋友。小W是个很怪的人，他觉得，每个小朋友应该分得编号连续的一段糖果，而且每个小朋友至少应该得到一颗糖果。奇怪的不知这一点，小W给每颗糖果一个值用来表示它的美味度(可以为负数)，作为一个绝对公平的追求者，他当然希望将所有糖果公平的分给所有小朋友，所以他希望这些小朋友所得到的最大糖果美味值之和尽量小。
小W定制了这样一套奇怪的规则，他却不知道该如何分糖果了，这个艰巨的任务就交给了你。
输入格式
第一行两个整数N，k。
第二行N个数，第i个整数表示第i号糖果的美味值。
输出格式
仅一行一个数，表示最小的最大糖果美味值之和。
3 2
-1 -1 -2
-2
数据范围与约定
对于100%的数据，N<=20000 k<=N