시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB72475255551776936.192%

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

예제 입력 1

5 3
1
2
8
4
9

예제 출력 1

3

힌트

공유기를 1, 4, 8 또는 1, 4, 9에 설치하면 가장 인접한 두 공유기 사이의 거리는 3이고, 이 거리보다 크게 공유기를 3개 설치할 수 없다.

W3sicHJvYmxlbV9pZCI6IjIxMTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZjVcdWM3MjBcdWFlMzAgXHVjMTI0XHVjZTU4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIzYzRcdWQ2MDRcdWM3NzRcdWM3NTggXHVjOWQxIE5cdWFjMWNcdWFjMDAgXHVjMjE4XHVjOWMxXHVjMTIwIFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM5ZDFcdWM3NTggXHVjODhjXHVkNDVjXHViMjk0IHg8c3ViPjE8XC9zdWI+LCAuLi4sIHg8c3ViPk48XC9zdWI+XHVjNzc0XHVhY2UwLCBcdWM5ZDEgXHVjNWVjXHViN2VjXHVhYzFjXHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWM4OGNcdWQ0NWNcdWI5N2MgXHVhYzAwXHVjOWMwXHViMjk0IFx1Yzc3Y1x1Yzc0MCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjNjNFx1ZDYwNFx1Yzc3NFx1YjI5NCBcdWM1YjhcdWM4MWMgXHVjNWI0XHViNTE0XHVjMTFjXHViMDk4IFx1YzY0MFx1Yzc3NFx1ZDMwY1x1Yzc3NFx1Yjk3YyBcdWM5OTBcdWFlMzBcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YzlkMVx1YzVkMCBcdWFjZjVcdWM3MjBcdWFlMzAgQ1x1YWMxY1x1Yjk3YyBcdWMxMjRcdWNlNThcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViOWNlXHVjNzQwIFx1YWNmM1x1YzVkMFx1YzExYyBcdWM2NDBcdWM3NzRcdWQzMGNcdWM3NzRcdWI5N2MgXHVjMGFjXHVjNmE5XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1ZDU1YyBcdWM5ZDFcdWM1ZDBcdWIyOTQgXHVhY2Y1XHVjNzIwXHVhZTMwXHViOTdjIFx1ZDU1OFx1YjA5OFx1YjljYyBcdWMxMjRcdWNlNThcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHVhYzAwXHVjN2E1IFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWI0NTAgXHVhY2Y1XHVjNzIwXHVhZTMwIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWI5N2MgXHVhYzAwXHViMmE1XHVkNTVjIFx1ZDA2Y1x1YWM4YyBcdWQ1NThcdWM1ZWMgXHVjMTI0XHVjZTU4XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+Q1x1YWMxY1x1Yzc1OCBcdWFjZjVcdWM3MjBcdWFlMzBcdWI5N2MgTlx1YWMxY1x1Yzc1OCBcdWM5ZDFcdWM1ZDAgXHVjODAxXHViMmY5XHVkNzg4IFx1YzEyNFx1Y2U1OFx1ZDU3NFx1YzExYywgXHVhYzAwXHVjN2E1IFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWI0NTAgXHVhY2Y1XHVjNzIwXHVhZTMwIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWI5N2MgXHVjZDVjXHViMzAwXHViODVjIFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM5ZDFcdWM3NTggXHVhYzFjXHVjMjE4IE4gKDIgJmxlOyBOICZsZTsgMjAwLDAwMClcdWFjZmMgXHVhY2Y1XHVjNzIwXHVhZTMwXHVjNzU4IFx1YWMxY1x1YzIxOCBDICgyICZsZTsgQyAmbGU7IE4pXHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM3NzRcdWMwYzFcdWM3NTggXHViZTQ4IFx1Y2U3OFx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM5ZDFcdWM3NTggXHVjODhjXHVkNDVjXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCB4PHN1Yj5pPFwvc3ViPiAoMCAmbGU7IHg8c3ViPmk8XC9zdWI+ICZsZTsgMSwwMDAsMDAwLDAwMClcdWFjMDAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzAwXHVjN2E1IFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWI0NTAgXHVhY2Y1XHVjNzIwXHVhZTMwIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhYzcwXHViOWFjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVhY2Y1XHVjNzIwXHVhZTMwXHViOTdjIDEsIDQsIDggXHViNjEwXHViMjk0IDEsIDQsIDlcdWM1ZDAgXHVjMTI0XHVjZTU4XHVkNTU4XHViYTc0IFx1YWMwMFx1YzdhNSBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViNDUwIFx1YWNmNVx1YzcyMFx1YWUzMCBcdWMwYWNcdWM3NzRcdWM3NTggXHVhYzcwXHViOWFjXHViMjk0IDNcdWM3NzRcdWFjZTAsIFx1Yzc3NCBcdWFjNzBcdWI5YWNcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzhjIFx1YWNmNVx1YzcyMFx1YWUzMFx1Yjk3YyAzXHVhYzFjIFx1YzEyNFx1Y2U1OFx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjExMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkFnZ3Jlc3NpdmUgY293cyIsImRlc2NyaXB0aW9uIjoiPHA+RmFybWVyIEpvaG4gaGFzIGJ1aWx0IGEgbmV3IGxvbmcgYmFybiwgd2l0aCBOICgyICZsdDs9IE4gJmx0Oz0gMjAwLDAwMCkgc3RhbGxzLiBUaGUgc3RhbGxzIGFyZSBsb2NhdGVkIGFsb25nIGEgc3RyYWlnaHQgbGluZSBhdCBwb3NpdGlvbnMgeDEsLi4uLHhOICgwICZsdDs9IHhpICZsdDs9IDEsMDAwLDAwMCwwMDApLjxcL3A+XHJcblxyXG48cD5IaXMgQyAoMiAmbHQ7PSBDICZsdDs9IE4pIGNvd3MgZG9uJiMzOTt0IGxpa2UgdGhpcyBiYXJuIGxheW91dCBhbmQgYmVjb21lIGFnZ3Jlc3NpdmUgdG93YXJkcyBlYWNoIG90aGVyIG9uY2UgcHV0IGludG8gYSBzdGFsbC4gVG8gcHJldmVudCB0aGUgY293cyBmcm9tIGh1cnRpbmcgZWFjaCBvdGhlciwgRkogd2FudCB0byBhc3NpZ24gdGhlIGNvd3MgdG8gdGhlIHN0YWxscywgc3VjaCB0aGF0IHRoZSBtaW5pbXVtIGRpc3RhbmNlIGJldHdlZW4gYW55IHR3byBvZiB0aGVtIGlzIGFzIGxhcmdlIGFzIHBvc3NpYmxlLiBXaGF0IGlzIHRoZSBsYXJnZXN0IG1pbmltdW0gZGlzdGFuY2U/PFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogTiBhbmQgQzxcL2xpPlxyXG5cdDxsaT5MaW5lcyAyLi5OKzE6IExpbmUgaSsxIGNvbnRhaW5zIGFuIGludGVnZXIgc3RhbGwgbG9jYXRpb24sIHhpPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogT25lIGludGVnZXI6IHRoZSBsYXJnZXN0IG1pbmltdW0gZGlzdGFuY2U8XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiI8cD5GSiBjYW4gcHV0IGhpcyAzIGNvd3MgaW4gdGhlIHN0YWxscyBhdCBwb3NpdGlvbnMgMSwgNCBhbmQgOCwgcmVzdWx0aW5nIGluIGEgbWluaW11bSBkaXN0YW5jZSBvZiAzLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > USA Computing Olympiad > 2004-2005 Season > USACO February 2005 Contest > Gold 3번