P1181 Sequence Segmentation Section I

Given a sequence $A_i$ of length $N$ consisting of non-negative integers, split it into several consecutive segments such that the sum of each segment does not exceed $M$ (it can be equal to $M$). Find the minimum number of segments needed to meet the requirement.

The first line contains two positive integers $N, M$, representing the length of the sequence $A_i$ and the maximum allowed sum of each segment. The second line contains $N$ space-separated non-negative integers $A_i$, as described.

Output a single integer: the minimum number of segments.

For $20\%$ of the testdata, there is $N≤10$. For $40\%$ of the testdata, there is $N≤1000$. For $100\%$ of the testdata, there are $N≤100000, M≤10^9$, $M$ is greater than the maximum element, and the sum of $A_i$ does not exceed $10^9$. Split the sequence as follows: $[4][2 4][5 1]$ The sum of the first segment is $4$, the sum of the $2$nd segment is $6$, and the sum of the $3$rd segment is $6$, all not exceeding $M=6$. It can be proven that $3$ is the minimum number of segments. Translated by ChatGPT 5