分数: 400 分
问题陈述
Takahashi 在一家运输公司负责交货计划。
今天,他需要制定一个计划来交付 N 包使用 K 卡车。
每个包裹的编号为 1 to N,以及包裹的重量 i is A_i.
为了提高配送效率,他决定对包裹进行整理 1, 2, \ldots, N 按此顺序并将它们分为 K 连续段,每个段至少包含 1 包裹,并将每个分段中的包裹分配给一辆卡车。每个包都属于一个段,并且段之间存在一一对应的关系 K 段和 K 卡车。
对于每辆卡车,分配给该卡车的包裹重量总和称为 负载 那辆卡车的 。
高桥希望最大化最小负载 K 卡车。
考虑所有可能的划分包裹的方式,找到“最小负载”的最大可能值 K 卡车。”
约束
- 1 \leq K \leq N \leq 10^5
- 1 \leq A_i \leq 10^9
- 所有输入均为整数。
输入
N K A_1 A_2 \ldots A_N
- 第一行包含一个整数 N 代表包裹数量和一个整数 K 代表卡车数量,以空格分隔。
- 第二行包含 N 整数 A_1, A_2, \ldots, A_N 代表每个包裹的重量,以空格分隔。
输出
在一行中打印最小负载的最大可能值 K 包裹被最佳分割时的卡车。
示例输入 1
5 2 1 2 3 4 5
示例输出 1
6
示例输入 2
7 3 3 1 4 1 5 9 2
示例输出 2
6
示例输入 3
10 4 100 200 150 300 50 250 400 100 350 200
示例输出 3
450