{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n \u003cp\u003eGiven an integer sequence { \u003ci\u003ea\u003csub\u003en\u003c/sub\u003e\u003c/i\u003e } of length \u003ci\u003eN\u003c/i\u003e, 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 \u003ci\u003eM\u003c/i\u003e. You are to find a cutting that minimizes the sum of the maximum integer of each part.\u003c/p\u003e\n \u003c/div\u003e\n给定一个长度为N的序列,你需要把序列分成很多段。每段的和不能超过M。每段的价值为这段的最大值。如何分割使得所有段的价值总和最小。"}},{"title":"Input","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n \u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003eThe first line of input contains two integer \u003ci\u003eN\u003c/i\u003e (0 \u0026lt; \u003ci\u003eN\u003c/i\u003e ≤ 100 000), \u003ci\u003eM\u003c/i\u003e. The following line contains \u003ci\u003eN\u003c/i\u003e integers describes the integer sequence. Every integer in the sequence is between 0 and 1 000 000 inclusively.\u003c/p\u003e\u003c/span\u003e\n \u003c/div\u003e\n输入第一行两个整数N (0 \u0026lt; \u003ci\u003eN\u003c/i\u003e ≤ 100 000),M\u003c/br\u003e\n第二行N个整数,范围[0,1000000]"}},{"title":"Output","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n \u003cp\u003eOutput one integer which is the minimum sum of the maximum integer of each part. If no such cuttings exist, output −1.\u003c/p\u003e\n \u003c/div\u003e\n输出每段最大之和的最小值。如果无法分割,输出-1"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e8 17\n2 2 2 8 1 8 2 1\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e12\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n \u003cp\u003eUse 64-bit integer type to hold \u003ci\u003eM\u003c/i\u003e.\u003c/p\u003e\n \u003c/div\u003e\n用64为int存储M"}}]}