BooBoo and Upsolving <Circuits>
Practice
3.9 (16 votes)
Binary search algorithm
Easy
Greedy algorithm
Ready
Open
Approved
Problem
75% Success 6889 Attempts 20 Points 1s Time Limit 256MB Memory 1024 KB Max Code

The hero of this story is a toddler named BooBoo. Inspired by the legendary competitive coder Gena, BooBoo has also started preparing to race to the top of the ranks.

BooBoo is going to practice N different problems in the exact given order over the next M days. For each problem, he writes down the amount of time \(q_i\) he will take to think and code the \(i^{th}\) problem (He is quite good at estimating!). Before starting on the problems, he took advice from experienced competitive programmers on his practice routine and almost all of them advised him to keep his daily load at the minimum possible and avoid over training.

Since BooBoo already has N problems to solve, he asks you to find the minimum time T such that training everyday for a time \(t_i \le T\) is sufficient to solve all the N problems in M days.

Note : Unlike in real world, you cannot think on a problem on one day and solve it on the other day. You need to do it on the very same day!

Input Format:

The first line contains two space separated integers N and M. The next line contains N space separated integers denoting the time \(q_i\) required to solve the \(i^{th}\) problem.

Output Format:

The output consists of one integer, the minimum time T as described in the problem statement.

Constraints:

\(1 \le N \le 10^5\)
\(1 \le M \le N\)
\(1 \le q_i \le 10^{12}\)

Subtasks

20 points: \(1 \le N \le 1000 , 1 \le M \le 100, 1 \le q_i \le 100\).
80 points: Original Constraints

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:10
14 votes
Tags:
AlgorithmsBasics of String ManipulationMath BasicModulus ArithmeticMathNumber Theory
Points:30
27 votes
Tags:
AlgorithmsDynamic Programming2D dynamic programmingC++
Points:20
16 votes
Tags:
AlgorithmsEasyString Manipulation