AT_abc319_d.[ABC319D] Minimum Width

普及-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

高桥君想要将由 $N$ 个单词组成的句子显示在窗口中。所有单词的纵向高度相同，第 $i$ 个单词（ $1 \leq i \leq N$ ）的横向宽度为 $L_i$ 。

句子在窗口中显示时，单词之间用宽度为 $1$ 的空格分隔。更严格地说，当高桥君在宽度为 $W$ 的窗口中显示句子时，需满足以下条件：

句子被分成若干行显示。
第 $1$ 个单词显示在最上面一行的开头。
第 $i$ 个单词（ $2 \leq i \leq N$ ）要么紧跟在第 $i-1$ 个单词后面，中间隔一个空格，要么显示在第 $i-1$ 个单词所在行的下一行的开头。除此之外不能出现在其他位置。
每一行的横向宽度不能超过 $W$ 。这里，行的宽度指的是从最左侧单词的左端到最右侧单词的右端的距离。

当高桥君将句子显示在窗口中时，句子正好被分成了 $M$ 行。请你求出可能的最小窗口宽度 $W$ 。

输入以如下格式从标准输入给出。

$N$ $M$ $L_1$ $L_2$ $\ldots$ $L_N$

请输出一个整数，表示可能的最小窗口宽度 $W$ 。

输入#2

10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

输出#2

10000000009

输入#3

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

输出#3

限制条件

当窗口宽度为 $26$ 时，可以如下图所示将给定的句子分成 $3$ 行显示。

当窗口宽度小于等于 $25$ 时，无法将句子分成 $3$ 行显示，因此应输出 $26$ 。
注意，不能将单词跨行显示，不能使行宽超过窗口宽度，也不能改变单词顺序。

请注意，答案可能超出 $32$ 位整数的范围。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?