Loading...
Loading...
Loading...
A study group of k students must cover a textbook of n chapters before the exam. The chapters are split into k blocks of consecutive chapters, one block per student, and every student gets at least one chapter. Each chapter has a known number of pages.
A student's load is the total pages of their block. Print the smallest possible value of the largest load. If there are more students than chapters, the split is impossible, so print -1.
-1.Example 1
Input
4 2 12 34 67 90
Output
113
Splitting as 12 34 67 and 90 gives loads 113 and 90. No split does better than 113.
Example 2
Input
3 5 10 20 30
Output
-1
Five students, but only three chapters.
Try the problem first. Open one hint at a time.
First handle k > n: some student would get no chapter, so print -1.
Fix a limit L. Walk through the chapters and give pages to one student until the next chapter would go over L. How many students do you need?
If a limit works with at most k students, any larger limit also works. Search for the smallest limit that works.
With at most k blocks possible, you can always cut a block further to reach exactly k students, because k ≤ n and no load grows.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor