Minimum Width

题目描述

Takahashi 在一个窗口中显示一个由 $N$ 个单词组成的句子。 所有单词具有相同的高度，第 $i$ 个单词 $(1\leq i\leq N)$ 的宽度为 $L _ i$。 单词在窗口中以宽度为 $1$ 的空格分隔。 更精确地说，当句子在宽度为 $W$ 的窗口中显示时，应满足以下条件。

句子被分成若干行。 第一个单词显示在顶行的开头。 第 $i$ 个单词 $(2\leq i\leq N)$ 要么在第 $(i-1)$ 个单词之后留下一个宽度为 $1$ 的间隙显示，要么显示在包含第 $(i-1)$ 个单词的那一行的下一行的开头。不会出现在其它位置。 每一行的宽度不超过 $W$。这里，一行的宽度指从最左边单词的左端到最右边单词的右端的距离。

当 Takahashi 在窗口中显示该句子时，句子能在 $M$ 行或更少的行内显示完毕。 求窗口的最小可能宽度。

输入格式

输入从标准输入按以下格式给出： $N$ $M$ $L _ 1$ $L _ 2$ $\ldots$ $L _ N$

输出格式

在一行中输出答案。

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\leq M\leq N\leq2\times10 ^ 5$ $1\leq L _ i\leq10^9\ (1\leq i\leq N)$ 所有输入值均为整数。当窗口宽度为 $26$ 时，你可以将给定句子放入三行，如下所示。 当窗口宽度为 $25$ 或更小的时候，不能将给定句子放入三行，所以输出 $26$。 注意不应将一个单词拆到多行展示，不应让一行的宽度超过窗口宽度，或重新排列单词。
注意答案可能无法用 $32\operatorname{bit}$ 整数表示。

标签: AtCoder|abc319D

来源

AtCoder|abc319D