3603 - [ABC319D] 最小窗口宽度
题目描述
犇犇是一名排版设计师，最近接到了一项紧急任务：将一篇由 N 个单词组成的文章排版到电子屏幕上。
每个单词的宽度各不相同，第 i 个单词（1 \leq i \leq N）的横向宽度为 L_i。所有单词的高度相同，因此只需要考虑横向排布。
排版时需要遵循以下规则：
- 单词按原文顺序依次排列，不能打乱顺序。
- 相邻两个单词之间必须用一个空格隔开（空格宽度为 1）。
- 每个单词要么紧跟在前一个单词后面（中间隔一个空格），要么换到下一行的开头。
- 每一行的总宽度不能超过屏幕的宽度 W。一行的宽度定义为从该行最左侧单词的左端到最右侧单词的右端的距离。
犇犇希望将这篇文章恰好排成 M 行。请你帮他计算出满足条件的最小屏幕宽度 W 是多少。
输入
第一行输入两个整数 N 和 M，分别表示单词数量和要求的行数。
第二行输入 N 个整数 L_1, L_2, \ldots, L_N，其中 L_i 表示第 i 个单词的宽度。
输出
输出一个整数，表示恰好排成 M 行时可能的最小窗口宽度 W。
样例
输入
13 3 9 5 2 7 1 8 8 2 1 5 2 3 6
输出
26
输入
10 1 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
输出
10000000009
输入
30 8 8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32 60
输出
189
说明
提示
样例1解释
当窗口宽度为 26 时，可以将文章恰好排成 3 行，如下图所示：
当窗口宽度小于等于 25 时，无法将文章排成 3 行，因此答案为 26。
注意：单词不能跨行显示，每行宽度不能超过窗口宽度，且不能改变单词顺序。
样例2解释
请注意，答案可能超出 32 位整数的范围。
数据范围
- 1 \leq M \leq N \leq 2 \times 10^5
- 1 \leq L_i \leq 10^9（1 \leq i \leq N）