문제
Farmer John은 그의 농장에서 새로운 소 사료 먹기 대회를 개최하고 있다!
전 세계에서 온 소들이 대회에 참가하고 풀을 먹기 위해 지역 공항에 도착하고 있다. 구체적으로, 공항에는 N마리의 소가 도착하며 (1≤N≤10^5), 소 i는 시간 ti에 도착한다 (0≤ti≤10^9). Farmer John은 소들을 공항에서 이동시키기 위해 M대의 버스를 준비해 두었다 (1≤M≤10^5). 각 버스는 최대 C마리의 소를 태울 수 있다 (1≤C≤N). Farmer John은 버스들과 함께 공항에서 기다리고 있으며, 도착하는 소들을 버스에 배정하고자 한다. 한 버스는 그 안에 있는 마지막 소가 도착한 시간에 출발할 수 있다. Farmer John은 좋은 주인이 되고 싶기 때문에 도착한 소들을 공항에서 너무 오래 기다리게 하고 싶지 않다. Farmer John이 버스들을 최적으로 조율할 때, 어떤 소든지 기다리는 시간의 최댓값의 가능한 가장 작은 값은 무엇인가? 소의 기다리는 시간은 그 소의 도착 시간과 배정된 버스의 출발 시간의 차이이다.
MC ≥ N임이 보장된다.
입력
첫 줄에는 공백으로 구분된 세 정수 N, M, C가 주어진다.
다음 줄에는 각 소의 도착 시간을 나타내는 N개의 정수가 공백으로 구분되어 주어진다.
출력
도착한 소들 중 어떤 소의 최대 대기 시간이 최소가 되도록 할 때, 그 값을 한 줄에 출력하라.
예제
6 3 2
1 1 10 14 4 3
4
만약 시간 1에 도착한 두 소를 한 버스에 태우고, 시간 3과 4에 도착한 소들을 두 번째 버스에, 시간 10과 14에 도착한 소들을 세 번째 버스에 태우면, 어떤 소가 기다리는 최대 시간은 4가 된다 (시간 10에 도착한 소는 10부터 14까지 기다린다).
로그인해야 코드를 작성할 수 있어요.