问题 AP: Cut the Sequence
内存限制:128 MB
时间限制:2.000 S
评测方式:文本比较
命题人:
提交:2
解决:2
题目描述
Given an integer sequencean an of length N, you are to cut the sequence into several parts every one of which is a consecutive subsequence of the original sequence. Every part must satisfy that the sum of the integers in the part is not greater than a given integer M. You are to find a cutting that minimizes the sum of the maximum integer of each part.
输入
The first line of input contains two integer N (0<N≤100000), M. The following line contains N integers describes the integer sequence. Every integer in the sequence is between 0 and 1 000 000 inclusively.
输出
Output one integer which is the minimum sum of the maximum integer of each part. If no such cuttings exist, output −1.
样例输入 复制
8 17
2 2 2 8 1 8 2 1
样例输出 复制
12
提示
Use 64-bit integer type to hold M.