Fewest Bounded Pieces

Difficulty: 1700 5000 ms 128 MB

greedy

Cut the array into the minimum number of contiguous pieces so each piece's sum is at most K. Print the minimum count, or −1 if some single element exceeds K.

Input: the first line has N and K; the second line has N positive integers.

Output: the minimum number of pieces, or −1.

Constraints:

• 1 ≤ N ≤ 10⁵
• 1 ≤ K ≤ 10⁹
• 1 ≤ a_i ≤ 1000

Sample Tests

5 6
1 2 3 4 5

3

3 2
1 5 1

-1

Read the Editorial