题目描述

对于给定的一个长度为 N 的正整数数列 A，现要将其分成 M 段，并要求每段连续，使得每段和的最大值尽可能小。

例如，将数列：

4 2 4 5 1

分成 3 段。

如果分为：

[4 2] [4 5] [1]

各段的和分别为 6、9、1，最大值为 9。

如果分为：

[4] [2 4] [5 1]

各段的和分别为 4、6、6，最大值为 6。

并且无论如何分段，最大值都不会小于 6。

所以答案为 6。

输入格式

第一行包含两个正整数 N、M。

第二行包含 N 个空格隔开的非负整数 A_i。

输出格式

输出一个正整数，表示将数列分成 M 段后，每段和的最大值的最小可能值。

输入数据 1

5 3
4 2 4 5 1

输出数据 1

6

数据范围与提示

对于 20% 的数据，N <= 10。

对于 40% 的数据，N <= 1000。

对于 100% 的数据，N <= 100000，M <= N，A_i 之和不超过 10^9。

本题可以使用二分答案：

• 猜测每段和的最大值为 x。
• 用 check(x) 判断能否在每段和不超过 x 的情况下，把数列分成不超过 M 段。
• 如果可以，说明 x 可能偏大，继续尝试更小的答案。
• 如果不可以，说明 x 太小，需要增大。