分数: 400 分
问题陈述
高桥有一根长绳子。
此绳子分为 N 部分,每个部分的编号为 1 to N 从左到右。截面长度 i (1 \leq i \leq N)是 A_i,绳子的总长度是 A_1 + A_2 + \cdots + A_N.
高桥想把这条绳子准确地分成 K 件。绳索只能在部分之间的边界处切断 i 和部分 i+1 (1 \leq i \leq N-1)。将绳子精确地分成 K 件,他准确选择 K - 1 的 N - 1 这些位置处的可用边界和切口。无法删除部分,并且每个部分必须恰好属于生成的部分之一。
因此,分割后的每一块都由一个或多个连续编号的部分组成。每一块的长度是它所包含的部分的长度之和。
高桥想要最小化最长片段的长度 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 代表的长度 N 部分,以空格分隔。
输出
在一行中打印最长的一段的最小可能长度 K 切割效果最佳时的碎片。
示例输入 1
5 3 1 2 3 4 5
示例输出 1
6
示例输入 2
8 4 3 1 4 1 5 9 2 6
示例输出 2
9
示例输入 3
10 3 100 200 300 400 500 600 700 800 900 1000
示例输出 3
2100