← 返回题目列表

AtCoder · awc0036_c

C. 分割日志

中文机器翻译题面 查看原题

分数: 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