P1182 Sequence Partitioning Section II

Given a sequence of positive integers $A_{1\sim N}$ of length $N$, you need to partition it into $M$ ($M \leq N$) contiguous segments, such that the maximum segment sum is minimized. About minimizing the maximum: For example, consider the sequence $4\ 2\ 4\ 5\ 1$ to be divided into $3$ segments. Partition it as: $$[4\ 2][4\ 5][1]$$ The sum of the first segment is $6$, the sum of the second segment is $9$, the sum of the third segment is $1$, and the maximum of these sums is $9$. Partition it as: $$[4][2\ 4][5\ 1]$$ The sum of the first segment is $4$, the sum of the second segment is $6$, the sum of the third segment is $6$, and the maximum of these sums is $6$. Moreover, no matter how you partition it, the maximum will not be smaller than $6$. Therefore, for the sequence $4\ 2\ 4\ 5\ 1$ divided into $3$ segments, the minimum possible maximum segment sum is $6$.

The first line contains two positive integers $N, M$. The second line contains $N$ space-separated non-negative integers $A_i$, as described above.

A single positive integer: the minimum possible value of the maximum segment sum.

Constraints: - For $20\%$ of the testdata, $N \leq 10$. - For $40\%$ of the testdata, $N \leq 1000$. - For $100\%$ of the testdata, $1 \leq N \leq 10^5$, $M \leq N$, $A_i < 10^8$, and the answer does not exceed $10^9$. Translated by ChatGPT 5