分数: 366 分
问题陈述
Takahashi 有一个日志,包括 N 部件连接成一排。零件已编号 1, 2, \ldots, N 从左到右,以及部分的长度 i is A_i.
相邻部分之间存在边界,并且存在 N - 1 这样的界限。即,部分之间的边界 i 和部分 i + 1 (1 \leq i \leq N - 1)。高桥选择 K 对这些边界进行切割,将日志分为 K + 1 片段。
每个片段的长度由该片段中包含的部分的长度之和确定。让 M 是其中的最大长度 K + 1 片段。
找到以下的最小可能值 M 当切割位置被最佳选择时。
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N - 1
- 1 \leq A_i \leq 10^9
- 所有输入值均为整数。
输入
N K A_1 A_2 \ldots A_N
- 第一行包含一个整数 N 表示零件数和整数 K 代表剪切次数,以空格分隔。
- 第二行包含整数 A_1, A_2, \ldots, A_N 表示各部分的长度,以空格分隔。
输出
在一行中打印以下值的最小值 M,其中的最大长度 K + 1 片段,当切割位置被最佳选择时。
示例输入 1
5 2 3 5 4 7 6
示例输出 1
11
示例输入 2
4 1 1 2 3 4
示例输出 2
6
示例输入 3
10 3 5 8 3 12 7 2 9 6 4 10
示例输出 3
19
示例输入 4
20 5 14 7 23 11 5 19 8 30 12 6 17 25 3 9 21 16 28 4 13 10
示例输出 4
55
示例输入 5
2 1 1000000000 1000000000
示例输出 5
1000000000