主页 讨论版 问题 名次 状态 统计
12月将举办首届西电ACM新生赛,敬请期待~~~~
问题 M: 修理电线

问题 M: 修理电线

时间限制: 1 Sec  内存限制: 128 MB
提交: 93  解决: 41
[提交][状态][讨论版]

题目描述

又到了严酷的夏日,这是电厂老板狗头吕每年最头痛的时候。

因为用电负载量过大,经常导致电线gg,这个时候就需要派遣电工去进行修理。

一天,又有一条电线gg了。由于电线是一段一段的,吕老板已经确定了有连续的 m 段出现了损坏,于是他派出 k 个工人去修理。

考虑到工人们不想来回跑,所以要给每个工人分配一个连续的修复区间。

工人的修复区间不能有重合,否则他们会偷懒。

现请你帮助吕老板,来尽快修复电线,每个工人的修复速度都是一样的,修复所有损坏段后才算完成。

输入

多组数据

第一行两个第一行两个整数 m,k;( 1 <= k, m <= 100000)

第二行m个整数,Ti ,分别表示修理第 i 段电线所需时间。(1 <= Ti <= 1000)

输出

每组数据一行,一个整数,即修复电线的最少用时。

样例输入

9 3
1 2 3 4 5 6 7 8 9

样例输出

17

提示

样例,第一个工人修1 2 3 4 5,用时15


第二个工人修 6 7,用时 13


第三个工人修 8 9,用时 17


所以 17 时间后才能修完

[提交][状态][讨论版]