Informatica Online Judge

  민제의 마계행 포탈 [2391 / 0957]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 1   Total Tried : 1


The Champion of this Problem (C++) : gs17016 - ms / 1231byte
My Best Submission (C++) : N/A

[35th 김병국(gs17016)]
Writer ID : [gs17016]

Background

서현중로에서 교준이의 IOI점수와 같은 길이의 은신처에 숨지 못했던 민제는 아쉽게도 교준이에게서 도망치지 못해 감옥에 갇히고 말았다.
절대 민제가 도망치게 둘 수 없던 교준이는 민제를 마계로 보내기로 결정했다.
민제를 마계에 보내기 위해서는 K개의 포탈을 만들어야 한다.
현재 교준이는 N개의 포탈 부품이 있고, 각 부품마다 고유번호가 있다.
이 고유번호는 P이하의 자연수이다.
만약 포탈 부품을 다 사용하지 않고 남기면 민제가 들고 재조합할 가능성이 있기 때문에 모두 사용해야 한다.
현재 마계에서는 복잡도가 M을 초과하는 포탈을 만드는 행위를 금지하고 있어서 복잡도를 M이하로 만들어야 한다.
포탈의 복잡도는 다음과 같이 정의된다.
먼저, 포탈의 주축이 되는 두 부품을 설정한다. 이 두 부품은 각각 포탈에서 가장 작은 고유번호를 가진 부품과 가장 큰 고유번호를 가진 부품이어야 한다.
그리고 주축으로 사용하지 않은 부품들 중 일부 부품으로 경로를 직선으로 생성한다.
이 경로는 양쪽 끝이 주축에 연결되어 있으며, 이 경로의 개수가 포탈의 복잡도가 된다. 또한, 각 경로 내부에 있는 부품들 또한 연결되어 있다.
그러나, 주축을 잡지 않고 포탈 부품 하나만으로도 포탈을 만들 수 있는데, 이 경우 포탈의 복잡도는 0이 된다.
현재 교준이는 민제가 또 도망칠것 같아 초조한 상태이기 때문에 포탈을 최대한 빨리 만들어야한다.
포탈을 만드는데 걸리는 시간은 그 포탈에 있는 연결된 두 부품의 고유번호의 차이의 최대값이다.
예를 들어 주축으로 사용되는 포탈의 부품의 고유번호가 1, 5이고 복잡도가 2인 포탈이 있다.
포탈의 경로에 있는 부품들의 고유번호가 각각 (2, 3), (4)이면 이 포탈을 만드는데 걸리는 시간은 max(abs(1-2), abs(2-3), abs(3-5), abs(1-4), abs(4-5)) = 3이다.
만약 포탈이 하나의 부품으로 이루어져 있다면 그 포탈을 만드는데 걸리는 시간은 0이 된다.
N개의 부품으로 복잡도가 M이하인 포탈 K개를 만드는데 걸리는 최소 시간을 구하여라.
(단, 각 포탈의 복잡도는 M이하의 수 중 최대여야 한다.)

Input

첫 번째 줄에는 부품의 개수인 N, 복잡도의 상한선인 M, 포탈의 개수인 K가 입력된다.
두 번째 줄에는 N개의 부품에 적힌 숫자들이 입력된다.


[입력값의 정의역]
2<=N<=50000
1<=M<=15
1<=P<=10^9
1<=K<=N

Output

주어지는 입력에 대하여 포탈들을 만드는데 걸리는 최소 시간을 출력하여라.

IO Example

입력
4 2 1
4 3 7 1

출력
4

설명
주축을 1, 7이 적힌 부품으로 하고 복잡도를 2로 하면 포탈의 경로에 있는 부품들의 고유번호가 각각 (3), (4)가 되므로 포탈을 만드는데 걸리는 시간은 4이다.
만약 주축을 1, 7이 적힌 부품으로 하고 복잡도를 1로 하면 포탈의 경로에 있는 부품들의 고유번호가 각각 (3, 4)가 되어 포탈을 만드는데 걸리는 시간이 3이다.
그러나 위처럼 똑같은 부품들로 복잡도가 2인 포탈을 만들 수 있으므로 이 경우는 불가능하다.
따라서 포탈을 만드는데 걸리는 최소 시간은 4가 된다.

입력
11 3 2
1 2 3 4 10 11 12 13 14 15 16

출력
3

설명
주축을 1, 4이 적힌 부품으로 하고 복잡도를 2로 하면 포탈의 경로에 있는 부품들의 고유번호가 각각 (2), (3)이 되므로 이 포탈을 만드는데 걸리는 시간은 2이다.
주축을 10, 16이 적힌 부품으로 하고 복잡도를 3으로 하면 포탈의 경로에 있는 부품들의 고유번호가 각각 (11, 14), (12, 15), (13)이 되어 이 포탈을 만드는데 걸리는 시간은 3이다.
따라서 포탈을 만드는데 걸리는 최소 시간은 3이 된다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]