Question

TikTok | OA Coding Questions and Solutions | Set - 5 | 2022

Answer 1

Given an integer sequence (a) of length N, you are to cut the sequence into several parts such that every one of which is a consecutive subsequence of the original sequence. Every part must satisfy this-the sum of the integers in the part is not greater than a given integer M. You are to find a cut that minimizes the sum of the maximum integer of each part.

 

Input

 

Given N(0 <N's 100 000), M, and N integers describes the integer sequence. Every Integer in the sequence is between 0 and 1 000 000 inclusively.

 

Output

 

Output one integer which is the minimum sum of the maximum integer of each part. If no such cutting exist output-1.

Comments

where do i find solution for this