Guitar Lesson
InterviewTime limit2sMemory limit128 MB
Split an ordered array into M contiguous groups so the maximum group sum is as small as possible, using binary search on the answer.
- Level
Medium4 of 10
- Topics
- Binary search, Greedy, Prefix sum
- Solved
- No attempts yet
Problem
An instructor wants to record guitar lecture videos onto several Blu-ray discs in order. The lectures must be recorded in their original order, because changing the order would break the flow of the course. Therefore, if lecture i and lecture j are recorded on the same disc, every lecture between them must also be recorded on that same disc.
The instructor has decided to store all lectures on exactly M Blu-ray discs. Every disc must have the same capacity, and each lecture must fit entirely on one disc. Find the minimum possible disc capacity.
Input
The first line contains the number of lectures N and the number of Blu-ray discs M. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ N)
The second line contains the lecture lengths in order, measured in minutes as positive integers. Each lecture length is at most 10,000 minutes.
Output
Print the minimum possible Blu-ray capacity on the first line.
Hint
Consider the case with 9 lectures and 3 discs. If lectures 1 through 5 go on the first disc, lectures 6 and 7 on the second disc, and lectures 8 and 9 on the third disc, the total lengths are 15, 13, and 17. Since every disc must have the same capacity, the required capacity is 17, and no smaller capacity can store all lectures.