P1295 [TJOI2011] Bookshelf

Since you have recently bought many books, you plan to make a new bookshelf in your study. To keep the overall style, you want the bookshelf’s width to be as small as possible. The bookshelf is placed against a wall; the width refers to the distance it occupies in the direction perpendicular to the wall.

You are given, in a fixed order, all the books to be placed on the bookshelf. There are $n$ books, and the $i$-th book has a length $h_i$. The bookshelf has several layers (shelves). The widths of different layers may vary, but the width of a layer cannot be smaller than the length of any book placed on that layer. At the same time, the sum of the lengths of the books on each layer cannot exceed a given parameter $m$, and the books on any layer must be a contiguous subsequence in the given order. The width of the bookshelf is the sum of the widths of all layers. Find the minimum possible width of the bookshelf.

The first line contains two integers $n$ and $m$. From line $2$ to line $(n + 1)$, each line contains one integer. The integer on line $(i + 1)$ is the length $h_i$ of the $i$-th book.

Output a single integer on one line representing the answer.

Constraints - For $30\%$ of the testdata, it is guaranteed that $n \leq 10^3$. - For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 10^5$, $1 \leq h_i \leq 10^9$, $\max\limits_{i = 1}^{n} h_i \leq m \leq 10^9$. Hint Because the original statement was quite ambiguous, here is a simplified version: Given a sequence $h$ of length $n$, partition $h$ into several segments such that the sum of numbers in each segment does not exceed $m$, and minimize the sum of the maximum values of all segments. Translated by ChatGPT 5