LCC/Moose '20 Contest 2 S3 - Alan's Got Cake 😳

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 5.0s
Memory limit: 256M

Problem types

Alan has a circular cake which he wants to share with his K friends. Unfortunately, this cake is notoriously difficult to cut, and thus the company who supplied the cake also included N dents in various locations that are easier to cut through. The N dents separate the cake into N sections each with an integer size a_i. Since Alan is a good friend, after the cake is cut he will take the smallest remaining piece. However, Alan loves cake, so he wants to cut at K of the N dents such that the smallest remaining piece is as large as possible. Can you help him?

Input Specification

The first line contains two integers N\ (1 \leq N \leq 10^5),K (1 \leq K \leq N).

The next line contains N integers a_i\ (1 \leq a_i \leq 10^9).

Output Specification

The only line of output is to contain one integer, the maximum length of the smallest piece.


Subtask 1 (30%)

N \leq 10^3

Subtask 2 (70%)

No further constraints.

Sample Input

5 3
5 2 6 9 3

Sample Output


Sample Explanation

Alan cuts between 5 and 2, between 6 and 9, and between 9 and 3, leaving the cake with 3 pieces of size 8, 9, and 8.


There are no comments at the moment.