페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5804

환경부의 나무 심기 프로젝트 1초 256MB

문제

정올시는 직선상의 N개의 가로수를 심을 수 있는 위치 x_1, ..., x_N의 좌표를 가지고 있으며, 중복된 좌표는 없다.

환경부에서 정올시에 나무를 C그루 심도록 명령을 하였는데, 나무들이 건강하게 자라기 위해서는 최대한 서로 멀리 떨어져서 심는 것이 좋다.

그래서 정올시의 시장은 가장 인접한 두 나무 사이의 거리를 최대한 크게 하려고 한다.

C그루의 나무를 N개의 위치에 적절히 심어, 가장 인접한 두 나무 사이의 거리를 최대로 하는 방법을 알아보자.


입력

첫 줄에 나무를 심을 수 있는 위치의 수 N (2 ≤ N ≤ 200,000)과 나무의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다.

둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 x_i (0 ≤ x_i ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.


출력

첫 줄에 가장 인접한 두 나무 사이의 최대 거리를 출력하시오.


예제1

입력
53
1
2
8
4
9
출력
3

나무를 1, 4, 8 또는 1, 4, 9에 심으면 가장 인접한 두 나무 사이의 거리는 3이고, 이 거리보다 크게 나무들을 심을 수는 없다.


태그

출처

USACO 2005 February Gold

역링크