AT_abc319_d [ABC319D] Minimum Width

题目描述

高桥君想要将由 $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$。

输入输出样例 #1

输入 #1

13 3
9 5 2 7 1 8 8 2 1 5 2 3 6

输出 #1

26

输入输出样例 #2

输入 #2

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

输出 #2

10000000009

输入输出样例 #3

输入 #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

189

说明/提示

限制条件

• $1 \leq M \leq N \leq 2 \times 10^5$
• $1 \leq L_i \leq 10^9$（$1 \leq i \leq N$）
• 输入均为整数

样例解释 1

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

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

样例解释 2

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

由 ChatGPT 4.1 翻译