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

문제

도현이의 집 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개 설치할 수 없다.

W3sicHJvYmxlbV9pZCI6IjIxMTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZjVcdWM3MjBcdWFlMzAgXHVjMTI0XHVjZTU4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIzYzRcdWQ2MDRcdWM3NzRcdWM3NTggXHVjOWQxIE5cdWFjMWNcdWFjMDAgXHVjMjE4XHVjOWMxXHVjMTIwIFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM5ZDFcdWM3NTggXHVjODhjXHVkNDVjXHViMjk0Jm5ic3A7eDxzdWI+MTxcL3N1Yj4sIC4uLiwgeDxzdWI+TjxcL3N1Yj5cdWM3NzRcdWFjZTAsIFx1YzlkMSBcdWM1ZWNcdWI3ZWNcdWFjMWNcdWFjMDAgXHVhYzE5XHVjNzQwIFx1Yzg4Y1x1ZDQ1Y1x1Yjk3YyBcdWFjMDBcdWM5YzBcdWIyOTQgXHVjNzdjXHVjNzQwIFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViM2M0XHVkNjA0XHVjNzc0XHViMjk0IFx1YzViOFx1YzgxYyBcdWM1YjRcdWI1MTRcdWMxMWNcdWIwOTggXHVjNjQwXHVjNzc0XHVkMzBjXHVjNzc0XHViOTdjIFx1Yzk5MFx1YWUzMFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjOWQxXHVjNWQwIFx1YWNmNVx1YzcyMFx1YWUzMCBDXHVhYzFjXHViOTdjIFx1YzEyNFx1Y2U1OFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWI5Y2VcdWM3NDAgXHVhY2YzXHVjNWQwXHVjMTFjIFx1YzY0MFx1Yzc3NFx1ZDMwY1x1Yzc3NFx1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVkNTVjIFx1YzlkMVx1YzVkMFx1YjI5NCBcdWFjZjVcdWM3MjBcdWFlMzBcdWI5N2MgXHVkNTU4XHViMDk4XHViOWNjIFx1YzEyNFx1Y2U1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWFjMDBcdWM3YTUgXHVjNzc4XHVjODExXHVkNTVjIFx1YjQ1MCBcdWFjZjVcdWM3MjBcdWFlMzAgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVkMDZjXHVhYzhjIFx1ZDU1OFx1YzVlYyBcdWMxMjRcdWNlNThcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5DXHVhYzFjXHVjNzU4IFx1YWNmNVx1YzcyMFx1YWUzMFx1Yjk3YyBOXHVhYzFjXHVjNzU4IFx1YzlkMVx1YzVkMCBcdWM4MDFcdWIyZjlcdWQ3ODggXHVjMTI0XHVjZTU4XHVkNTc0XHVjMTFjLCBcdWFjMDBcdWM3YTUgXHVjNzc4XHVjODExXHVkNTVjIFx1YjQ1MCBcdWFjZjVcdWM3MjBcdWFlMzAgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWNkNWNcdWIzMDBcdWI4NWMgXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzlkMVx1Yzc1OCBcdWFjMWNcdWMyMTggTiAoMiAmbGU7IE4gJmxlOyAyMDAsMDAwKVx1YWNmYyBcdWFjZjVcdWM3MjBcdWFlMzBcdWM3NTggXHVhYzFjXHVjMjE4IEMgKDIgJmxlOyBDICZsZTsgTilcdWM3NzQgXHVkNTU4XHViMDk4IFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWJlNDggXHVjZTc4XHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI0NTBcdWFjZTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzlkMVx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IHg8c3ViPmk8XC9zdWI+ICgwICZsZTsgeDxzdWI+aTxcL3N1Yj4gJmxlOyAxLDAwMCwwMDAsMDAwKVx1YWMwMCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCZuYnNwO1x1YWMwMFx1YzdhNSBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViNDUwIFx1YWNmNVx1YzcyMFx1YWUzMCBcdWMwYWNcdWM3NzRcdWM3NTggXHVjZDVjXHViMzAwIFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YWNmNVx1YzcyMFx1YWUzMFx1Yjk3YyAxLCA0LCA4IFx1YjYxMFx1YjI5NCAxLCA0LCA5XHVjNWQwIFx1YzEyNFx1Y2U1OFx1ZDU1OFx1YmE3NCBcdWFjMDBcdWM3YTUgXHVjNzc4XHVjODExXHVkNTVjIFx1YjQ1MCBcdWFjZjVcdWM3MjBcdWFlMzAgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YWM3MFx1YjlhY1x1YjI5NCAzXHVjNzc0XHVhY2UwLCBcdWM3NzQgXHVhYzcwXHViOWFjXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM4YyBcdWFjZjVcdWM3MjBcdWFlMzBcdWI5N2MgM1x1YWMxYyBcdWMxMjRcdWNlNThcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjIxMTAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBZ2dyZXNzaXZlIGNvd3MiLCJkZXNjcmlwdGlvbiI6IjxwPkZhcm1lciBKb2huIGhhcyBidWlsdCBhIG5ldyBsb25nIGJhcm4sIHdpdGggTiAoMiAmbHQ7PSBOICZsdDs9IDIwMCwwMDApIHN0YWxscy4gVGhlIHN0YWxscyBhcmUgbG9jYXRlZCBhbG9uZyBhIHN0cmFpZ2h0IGxpbmUgYXQgcG9zaXRpb25zIHgxLC4uLix4TiAoMCAmbHQ7PSB4aSAmbHQ7PSAxLDAwMCwwMDAsMDAwKS48XC9wPlxyXG5cclxuPHA+SGlzIEMgKDIgJmx0Oz0gQyAmbHQ7PSBOKSBjb3dzIGRvbiYjMzk7dCBsaWtlIHRoaXMgYmFybiBsYXlvdXQgYW5kIGJlY29tZSBhZ2dyZXNzaXZlIHRvd2FyZHMgZWFjaCBvdGhlciBvbmNlIHB1dCBpbnRvIGEgc3RhbGwuIFRvIHByZXZlbnQgdGhlIGNvd3MgZnJvbSBodXJ0aW5nIGVhY2ggb3RoZXIsIEZKIHdhbnQgdG8gYXNzaWduIHRoZSBjb3dzIHRvIHRoZSBzdGFsbHMsIHN1Y2ggdGhhdCB0aGUgbWluaW11bSBkaXN0YW5jZSBiZXR3ZWVuIGFueSB0d28gb2YgdGhlbSBpcyBhcyBsYXJnZSBhcyBwb3NzaWJsZS4gV2hhdCBpcyB0aGUgbGFyZ2VzdCBtaW5pbXVtIGRpc3RhbmNlPzxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IFR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IE4gYW5kIEM8XC9saT5cclxuXHQ8bGk+TGluZXMgMi4uTisxOiBMaW5lIGkrMSBjb250YWlucyBhbiBpbnRlZ2VyIHN0YWxsIGxvY2F0aW9uLCB4aTxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IE9uZSBpbnRlZ2VyOiB0aGUgbGFyZ2VzdCBtaW5pbXVtIGRpc3RhbmNlPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiPHA+RkogY2FuIHB1dCBoaXMgMyBjb3dzIGluIHRoZSBzdGFsbHMgYXQgcG9zaXRpb25zIDEsIDQgYW5kIDgsIHJlc3VsdGluZyBpbiBhIG1pbmltdW0gZGlzdGFuY2Ugb2YgMy48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

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