시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB95836826842.072%

문제

수열이 주어졌을 때, M을 수열의 모든 두 원소의 차이 중 가장 큰 값이라고 한다. m은 그 차이 중 가장 작은 값이라고 한다.

크기가 N인 수열 V가 주어진다. 여기서 K개 수를 적절히 제거해서 M+m을 가능한 작게 만드는 프로그램을 작성하시오.

입력

첫째 줄에 N(3 ≤ N ≤ 1,000,000)과 K(1 ≤ K ≤ N-2)가 주어진다.

둘째 줄에 V의 원소가 공백으로 구분되어 주어진다. (-5,000,000 ≤ Vi ≤ 5,000,000)

출력

첫째 줄에 가장 작은 M+m을 출력한다.

예제 입력 1

5 2
-3 -2 3 8 6

예제 출력 1

7

예제 입력 2

6 2
-5 8 10 1 13 -1

예제 출력 2

13

예제 입력 3

6 3
10 2 8 17 2 17

예제 출력 3

6
W3sicHJvYmxlbV9pZCI6IjM5ODgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMTggXHVhY2UwXHViOTc0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMyMThcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgTVx1Yzc0NCBcdWMyMThcdWM1ZjRcdWM3NTggXHViYWE4XHViNGUwIFx1YjQ1MCBcdWM2ZDBcdWMxOGNcdWM3NTggXHVjYzI4XHVjNzc0IFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YWMxMlx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIG1cdWM3NDAgXHVhZGY4IFx1Y2MyOFx1Yzc3NCBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWFjMTJcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQwNmNcdWFlMzBcdWFjMDAgTlx1Yzc3OCBcdWMyMThcdWM1ZjQgVlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzVlY1x1YWUzMFx1YzExYyBLXHVhYzFjIFx1YzIxOFx1Yjk3YyBcdWM4MDFcdWM4MDhcdWQ3ODggXHVjODFjXHVhYzcwXHVkNTc0XHVjMTFjIE0rbVx1Yzc0NCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjNzkxXHVhYzhjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOKDMgJmxlOyBOICZsZTsgMSwwMDAsMDAwKVx1YWNmYyBLKDEgJmxlOyBLICZsZTsgTi0yKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDAgVlx1Yzc1OCBcdWM2ZDBcdWMxOGNcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgtNSwwMDAsMDAwICZsZTsgVjxzdWI+aTxcL3N1Yj4gJmxlOyA1LDAwMCwwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIE0rbVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzk4OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJBWkxJS0EiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvJiMzOTtzIG5ld2VzdCBtYXRoIGhvbWV3b3JrIGFzc2lnbm1lbnQgaXMgYSB2ZXJ5IGRpZmZpY3VsdCBvbmUhIEdpdmVuIGEgc2VxdWVuY2UsIFYsIG9mIE4gaW50ZWdlcnMsIHJlbW92ZSBleGFjdGx5IEsgb2YgdGhlbSBmcm9tIHRoZSBzZXF1ZW5jZS4gTGV0IE0gYmUgdGhlIGxhcmdlc3QgZGlmZmVyZW5jZSBvZiBhbnkgdHdvIHJlbWFpbmluZyBudW1iZXJzIGluIHRoZSBzZXF1ZW5jZSwgYW5kIG0gdGhlIHNtYWxsZXN0IHN1Y2ggZGlmZmVyZW5jZS4gU2VsZWN0IHRoZSBLIGludGVnZXJzIHRvIGJlIHJlbW92ZWQgZnJvbSBWIGluIHN1Y2ggYSB3YXkgdGhhdCB0aGUgc3VtIE0gKyBtIGlzIHRoZSBzbWFsbGVzdCBwb3NzaWJsZS4gTWlya28gaXNuJiMzOTt0IHZlcnkgZ29vZCBhdCBtYXRoLCBzbyBoZSBoYXMgYXNrZWQgeW91IHRvIGhlbHAgaGltISZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIHBvc2l0aXZlIGludGVnZXJzLCBOICgzICZsZTsgTiAmbGU7IDEgMDAwIDAwMCkgYW5kIEsgKDEgJmxlOyBLICZsZTsgTiAtIDIpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgTiBzcGFjZS1zZXBhcmF0ZWQgcG9zaXRpdmUgaW50ZWdlcnMgJm5kYXNoOyB0aGUgc2VxdWVuY2UgViAoLTUgMDAwIDAwMCAmbGU7IFY8c3ViPmk8XC9zdWI+ICZsZTsgNSAwMDAgMDAwKS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSBzbWFsbGVzdCBwb3NzaWJsZSBzdW0gTSArIG0uJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #4 4번

  • 문제를 번역한 사람: baekjoon
  • 데이터를 추가한 사람: rdd6584