시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 249 100 87 44.162%

문제

GSHS에서는 체력측정에서 제자리 멀리뛰기가 가장 중요하다. GSHS의 체육선생님께서는 학생들의 제자리 멀리뛰기 실력을 키워주게 하기 위해서 특수 훈련을 준비중이다.

특수 훈련장소는 GSHS특수 트레이닝 센터로 이 곳은 끓는 용암으로 가득 차 있다. 체육선생님께서는 이 용암으로 가득찬 방의 가운데 있는 돌섬에 학생들을 가두고 학생들이 탈출해 나오기를 기대하고 있다. 탈출할 수 있는 방법은 단 한가지 이다. 돌섬에서 탈출구까지 띄엄 띄엄 존재하는 작은 돌섬들로 점프하여 탈출구까지 가는 것이다.

돌섬에서 탈출구 사이에는 총 n개의 작은 돌섬이 있다. 선생님은 이 n개의 작은 돌섬들 중 m개를 제거하여 학생들이 최대한 멀리뛰기 연습의 효율을 높이기 위해서 학생들이 각 돌섬을 점프한 거리의 최솟값을 최대한 크게 하려고 한다. 물론 학생들은 체력이 좋기 때문에 두 돌섬이 아무리 멀더라도 점프할 수 있다. 즉, 빠지는 일은 없다.

그리고 학생들은 탈출 시 n-m개의 모든 돌섬을 밟으면서 탈출해야 한다.

학 생들이 갇힌 돌섬으로부터 탈출구까지의 거리 d가 주어지고, 각 n개의 작은 돌섬의 위치(갇힌 돌섬으로 부터의 거리)가 주어지며, 제거할 수 있는 작은 돌섬의 수 m이 주어질 때, m개를 제거한 후 학생들이 점프하는 최소거리의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 갇힌 돌섬으로부터 탈출구까지의 거리 d(1 ≤ d ≤ 1,000,000,000), 작은 돌섬의 수 n(0 ≤ n ≤ 50,000), 제거할 수 있는 작은 돌섬의 수 m (0 ≤ m ≤ n)이 공백으로 구분되어 주어진다.

두 번째 줄부터 n줄에 걸쳐서 갇힌섬으로부터 각 작은 돌섬이 얼마나 떨어져 있는지를 나타내는 하나의 정수가 한 줄에 하나씩 주어진다. (단, 두 돌섬은 같은 위치에 있을 수 없다.)

출력

m개의 작은섬을 제거한 뒤 학생들이 점프할 수 있는 최소거리의 최댓값을 출력한다.

예제 입력 1

25 5 2
2
14
11
21
17

예제 출력 1

4
W3sicHJvYmxlbV9pZCI6IjYyMDkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MWNcdWM3OTBcdWI5YWMgXHViYTQwXHViOWFjXHViNmYwXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5HU0hTXHVjNWQwXHVjMTFjXHViMjk0IFx1Y2NiNFx1YjgyNVx1Y2UyMVx1YzgxNVx1YzVkMFx1YzExYyBcdWM4MWNcdWM3OTBcdWI5YWMgXHViYTQwXHViOWFjXHViNmYwXHVhZTMwXHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM5MTFcdWM2OTRcdWQ1NThcdWIyZTQuIEdTSFNcdWM3NTggXHVjY2I0XHVjNzIxXHVjMTIwXHVjMGRkXHViMmQ4XHVhZWQ4XHVjMTFjXHViMjk0IFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc1OCBcdWM4MWNcdWM3OTBcdWI5YWMgXHViYTQwXHViOWFjXHViNmYwXHVhZTMwIFx1YzJlNFx1YjgyNVx1Yzc0NCBcdWQwYTRcdWM2Y2NcdWM4ZmNcdWFjOGMgXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWQyYjlcdWMyMTggXHVkNmM4XHViODI4XHVjNzQ0IFx1YzkwMFx1YmU0NFx1YzkxMVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMmI5XHVjMjE4IFx1ZDZjOFx1YjgyOFx1YzdhNVx1YzE4Y1x1YjI5NCBHU0hTXHVkMmI5XHVjMjE4IFx1ZDJiOFx1YjgwOFx1Yzc3NFx1YjJkZCBcdWMxM2NcdWQxMzBcdWI4NWMgXHVjNzc0IFx1YWNmM1x1Yzc0MCBcdWIwNTNcdWIyOTQgXHVjNmE5XHVjNTU0XHVjNzNjXHViODVjIFx1YWMwMFx1YjRkZCBcdWNjMjggXHVjNzg4XHViMmU0LiBcdWNjYjRcdWM3MjFcdWMxMjBcdWMwZGRcdWIyZDhcdWFlZDhcdWMxMWNcdWIyOTQgXHVjNzc0IFx1YzZhOVx1YzU1NFx1YzczY1x1Yjg1YyBcdWFjMDBcdWI0ZGRcdWNjMmMgXHViYzI5XHVjNzU4IFx1YWMwMFx1YzZiNFx1YjM3MCBcdWM3ODhcdWIyOTQgXHViM2NjXHVjMTJjXHVjNWQwIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0NCBcdWFjMDBcdWI0NTBcdWFjZTAgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IFx1ZDBjOFx1Y2Q5Y1x1ZDU3NCBcdWIwOThcdWM2MjRcdWFlMzBcdWI5N2MgXHVhZTMwXHViMzAwXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVkMGM4XHVjZDljXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQwIFx1YjJlOCBcdWQ1NWNcdWFjMDBcdWM5YzAgXHVjNzc0XHViMmU0LiBcdWIzY2NcdWMxMmNcdWM1ZDBcdWMxMWMgXHVkMGM4XHVjZDljXHVhZDZjXHVhZTRjXHVjOWMwIFx1Yjc0NFx1YzVjNCBcdWI3NDRcdWM1YzQgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0IFx1Yzc5MVx1Yzc0MCBcdWIzY2NcdWMxMmNcdWI0ZTRcdWI4NWMgXHVjODEwXHVkNTA0XHVkNTU4XHVjNWVjIFx1ZDBjOFx1Y2Q5Y1x1YWQ2Y1x1YWU0Y1x1YzljMCBcdWFjMDBcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIzY2NcdWMxMmNcdWM1ZDBcdWMxMWMgXHVkMGM4XHVjZDljXHVhZDZjIFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBcdWNkMWQgblx1YWMxY1x1Yzc1OCBcdWM3OTFcdWM3NDAgXHViM2NjXHVjMTJjXHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjMTIwXHVjMGRkXHViMmQ4XHVjNzQwIFx1Yzc3NCBuXHVhYzFjXHVjNzU4IFx1Yzc5MVx1Yzc0MCBcdWIzY2NcdWMxMmNcdWI0ZTQgXHVjOTExIG1cdWFjMWNcdWI5N2MgXHVjODFjXHVhYzcwXHVkNTU4XHVjNWVjIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc3NCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViYTQwXHViOWFjXHViNmYwXHVhZTMwIFx1YzVmMFx1YzJiNVx1Yzc1OCBcdWQ2YThcdWM3MjhcdWM3NDQgXHViMTkyXHVjNzc0XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NzQgXHVhYzAxIFx1YjNjY1x1YzEyY1x1Yzc0NCBcdWM4MTBcdWQ1MDRcdWQ1NWMgXHVhYzcwXHViOWFjXHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHVkMDZjXHVhYzhjIFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YmIzY1x1Yjg2MCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDAgXHVjY2I0XHViODI1XHVjNzc0IFx1Yzg4Ylx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHViNDUwIFx1YjNjY1x1YzEyY1x1Yzc3NCBcdWM1NDRcdWJiMzRcdWI5YWMgXHViYTQwXHViMzU0XHViNzdjXHViM2M0IFx1YzgxMFx1ZDUwNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM5ODksIFx1YmU2MFx1YzljMFx1YjI5NCBcdWM3N2NcdWM3NDAgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI5YWNcdWFjZTAgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1ZDBjOFx1Y2Q5YyBcdWMyZGMgbi1tXHVhYzFjXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWIzY2NcdWMxMmNcdWM3NDQgXHViYzFmXHVjNzNjXHViYTc0XHVjMTFjIFx1ZDBjOFx1Y2Q5Y1x1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1OSBcdWMwZGRcdWI0ZTRcdWM3NzQgXHVhYzA3XHVkNzhjIFx1YjNjY1x1YzEyY1x1YzczY1x1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWQwYzhcdWNkOWNcdWFkNmNcdWFlNGNcdWM5YzBcdWM3NTggXHVhYzcwXHViOWFjIGRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwLCBcdWFjMDEgblx1YWMxY1x1Yzc1OCBcdWM3OTFcdWM3NDAgXHViM2NjXHVjMTJjXHVjNzU4IFx1YzcwNFx1Y2U1OChcdWFjMDdcdWQ3OGMgXHViM2NjXHVjMTJjXHVjNzNjXHViODVjIFx1YmQ4MFx1ZDEzMFx1Yzc1OCBcdWFjNzBcdWI5YWMpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVjODFjXHVhYzcwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNzkxXHVjNzQwIFx1YjNjY1x1YzEyY1x1Yzc1OCBcdWMyMTggbVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjLCBtXHVhYzFjXHViOTdjIFx1YzgxY1x1YWM3MFx1ZDU1YyBcdWQ2YzQgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IFx1YzgxMFx1ZDUwNFx1ZDU1OFx1YjI5NCBcdWNkNWNcdWMxOGNcdWFjNzBcdWI5YWNcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzA3XHVkNzhjIFx1YjNjY1x1YzEyY1x1YzczY1x1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWQwYzhcdWNkOWNcdWFkNmNcdWFlNGNcdWM5YzBcdWM3NTggXHVhYzcwXHViOWFjIGQoMSAmbGU7Jm5ic3A7ZCAmbGU7IDEsMDAwLDAwMCwwMDApLCBcdWM3OTFcdWM3NDAgXHViM2NjXHVjMTJjXHVjNzU4IFx1YzIxOCBuKDAgJmxlOyBuICZsZTsgNTAsMDAwKSwgXHVjODFjXHVhYzcwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNzkxXHVjNzQwIFx1YjNjY1x1YzEyY1x1Yzc1OCBcdWMyMTggbSAoMCAmbGU7IG0gJmxlOyZuYnNwO24pXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBuXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMFx1YzExYyBcdWFjMDdcdWQ3OGNcdWMxMmNcdWM3M2NcdWI4NWNcdWJkODBcdWQxMzAgXHVhYzAxIFx1Yzc5MVx1Yzc0MCBcdWIzY2NcdWMxMmNcdWM3NzQgXHVjNWJjXHViOWM4XHViMDk4IFx1YjVhOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyOTRcdWM5YzBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoXHViMmU4LCBcdWI0NTAgXHViM2NjXHVjMTJjXHVjNzQwIFx1YWMxOVx1Yzc0MCBcdWM3MDRcdWNlNThcdWM1ZDAgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM1YzZcdWIyZTQuKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPm1cdWFjMWNcdWM3NTggXHVjNzkxXHVjNzQwXHVjMTJjXHVjNzQ0IFx1YzgxY1x1YWM3MFx1ZDU1YyBcdWI0YTQgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IFx1YzgxMFx1ZDUwNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YzE4Y1x1YWM3MFx1YjlhY1x1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjYyMDkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSaXZlciBIb3BzY290Y2giLCJkZXNjcmlwdGlvbiI6IjxwPkV2ZXJ5IHllYXIgdGhlIGNvd3MgaG9sZCBhbiBldmVudCBmZWF0dXJpbmcgYSBwZWN1bGlhciB2ZXJzaW9uIG9mIGhvcHNjb3RjaCB0aGF0IGludm9sdmVzIGNhcmVmdWxseSBqdW1waW5nIGZyb20gcm9jayB0byByb2NrIGluIGEgcml2ZXIuIFRoZSBleGNpdGVtZW50IHRha2VzIHBsYWNlIG9uIGEgbG9uZywgc3RyYWlnaHQgcml2ZXIgd2l0aCBhIHJvY2sgYXQgdGhlIHN0YXJ0IGFuZCBhbm90aGVyIHJvY2sgYXQgdGhlIGVuZCwgTCB1bml0cyBhd2F5IGZyb20gdGhlIHN0YXJ0ICgxICZsdDs9IEwgJmx0Oz0gMSwwMDAsMDAwLDAwMCkuIEFsb25nIHRoZSByaXZlciBiZXR3ZWVuIHRoZSBzdGFydGluZyBhbmQgZW5kaW5nIHJvY2tzLCBOICgwICZsdDs9IE4gJmx0Oz0gNTAsMDAwKSBtb3JlIHJvY2tzIGFwcGVhciwgZWFjaCBhdCBhbiBpbnRlZ3JhbCBkaXN0YW5jZSBEaSBmcm9tIHRoZSBzdGFydCAoMCAmbHQ7IERpICZsdDsgTCkuPFwvcD5cclxuXHJcbjxwPlRvIHBsYXkgdGhlIGdhbWUsIGVhY2ggY293IGluIHR1cm4gc3RhcnRzIGF0IHRoZSBzdGFydGluZyByb2NrIGFuZCB0cmllcyB0byByZWFjaCB0aGUgZmluaXNoIGF0IHRoZSBlbmRpbmcgcm9jaywganVtcGluZyBvbmx5IGZyb20gcm9jayB0byByb2NrLiBPZiBjb3Vyc2UsIGxlc3MgYWdpbGUgY293cyBuZXZlciBtYWtlIGl0IHRvIHRoZSBmaW5hbCByb2NrLCBlbmRpbmcgdXAgaW5zdGVhZCBpbiB0aGUgcml2ZXIuPFwvcD5cclxuXHJcbjxwPkZhcm1lciBKb2huIGlzIHByb3VkIG9mIGhpcyBjb3dzIGFuZCB3YXRjaGVzIHRoaXMgZXZlbnQgZWFjaCB5ZWFyLiBCdXQgYXMgdGltZSBnb2VzIGJ5LCBoZSB0aXJlcyBvZiB3YXRjaGluZyB0aGUgdGltaWQgY293cyBvZiB0aGUgb3RoZXIgZmFybWVycyBsaW1wIGFjcm9zcyB0aGUgc2hvcnQgZGlzdGFuY2VzIGJldHdlZW4gcm9ja3MgcGxhY2VkIHRvbyBjbG9zZWx5IHRvZ2V0aGVyLiBIZSBwbGFucyB0byByZW1vdmUgc2V2ZXJhbCByb2NrcyBpbiBvcmRlciB0byBpbmNyZWFzZSB0aGUgc2hvcnRlc3QgZGlzdGFuY2UgYSBjb3cgd2lsbCBoYXZlIHRvIGp1bXAgdG8gcmVhY2ggdGhlIGVuZC4gSGUga25vd3MgaGUgY2Fubm90IHJlbW92ZSB0aGUgc3RhcnRpbmcgYW5kIGVuZGluZyByb2NrcywgYnV0IGhlIGNhbGN1bGF0ZXMgdGhhdCBoZSBoYXMgZW5vdWdoIHJlc291cmNlcyB0byByZW1vdmUgdXAgdG8gTSByb2NrcyAoMCAmbHQ7PSBNICZsdDs9IE4pLjxcL3A+XHJcblxyXG48cD5GSiB3YW50cyB0byBrbm93IGV4YWN0bHkgaG93IG11Y2ggaGUgY2FuIGluY3JlYXNlIHRoZSBzaG9ydGVzdCBkaXN0YW5jZSAqYmVmb3JlKiBoZSBzdGFydHMgcmVtb3ZpbmcgdGhlIHJvY2tzLiBIZWxwIEZhcm1lciBKb2huIGRldGVybWluZSB0aGUgZ3JlYXRlc3QgcG9zc2libGUgc2hvcnRlc3QgZGlzdGFuY2UgYSBjb3cgaGFzIHRvIGp1bXAgYWZ0ZXIgcmVtb3ZpbmcgdGhlIG9wdGltYWwgc2V0IG9mIE0gcm9ja3MuPFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVGhyZWUgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBMLCBOLCBhbmQgTTxcL2xpPlxyXG5cdDxsaT5MaW5lcyAyLi5OKzE6IEVhY2ggbGluZSBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIGluZGljYXRpbmcgaG93IGZhciBzb21lIHJvY2sgaXMgYXdheSBmcm9tIHRoZSBzdGFydGluZyByb2NrLiBObyB0d28gcm9ja3Mgc2hhcmUgdGhlIHNhbWUgcG9zaXRpb24uPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IEEgc2luZ2xlIGludGVnZXIgdGhhdCBpcyB0aGUgbWF4aW11bSBvZiB0aGUgc2hvcnRlc3QgZGlzdGFuY2UgYSBjb3cgaGFzIHRvIGp1bXAgYWZ0ZXIgcmVtb3ZpbmcgTSByb2NrczxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IjxwPkJlZm9yZSByZW1vdmluZyBhbnkgcm9ja3MsIHRoZSBzaG9ydGVzdCBqdW1wIHdhcyBhIGp1bXAgb2YgMiBmcm9tIDAgKHRoZSBzdGFydCkgdG8gMi4gQWZ0ZXIgcmVtb3ZpbmcgdGhlIHJvY2tzIGF0IDIgYW5kIDE0LCB0aGUgc2hvcnRlc3QgcmVxdWlyZWQganVtcCBpcyBhIGp1bXAgb2YgNCAoZnJvbSAxNyB0byAyMSBvciBmcm9tIDIxIHRvIDI1KS48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > USA Computing Olympiad > 2006-2007 Season > USACO December 2006 Contest > Silver 3번