ПУКАНКИ
Time limit0.2sMemory limit1024 MB
Split the line of N popcorn bags into K consecutive nonempty groups; find the minimum possible maximum group sum divided by eating speed S, rounded up.
- Level
Medium6 of 10
- Topics
- Binary search, Greedy, Prefix sum, Array
- Solved
- No attempts yet
Problem
„Мегамакс“ is holding a popcorn eating contest. Teams of K people take part. For the contest, N bags of popcorn are placed on a table in a straight line, and each team member takes several bags in a row, starting from the left. A member may take any number of bags, including none, if the previous member took the last one. The last team member takes all the remaining bags. The packaging must not be changed, and several team members must not share one bag. After the popcorn is distributed, a start signal is given and all participants begin eating their popcorn. The completion time is determined by the participant who eats their last piece of popcorn, rounded to an integer number of seconds.
The amount of popcorn in a bag can differ, so how the bags are distributed among the team members matters for making the eating time minimal. A person can eat exactly S pieces of popcorn per second.
Write a program popcorn that determines the minimal time to eat the popcorn.
Input
The first line of the standard input contains three integers: the number of popcorn bags N, the number of team members K, and the eating speed S.
The next line contains N integers Pi, the number of pieces of popcorn in bag i, counted from left to right.
Output
The standard output must contain one integer: the minimal time to eat the popcorn according to the contest rules.
Constraints
- 1 ≤ N ≤ 105
- 1 ≤ K ≤ 105
- 1 ≤ S ≤ 50
- 1 ≤ Pi ≤ 104