문제
석표의 미술관에는 N개의 그림이 전시되어 있다.
미술관은 긴 복도 형태이며 입구에서 X_i미터 떨어진 곳에 i번 그림이 있다.
또, 각 그림에는 가치가 있어 i번 그림은 V_i의 가치를 가진다.
석표는 미술품들을 아름답게 다시 전시 하고 싶다.
석표는 M개의 미술품만을 남겨두고 나머지 그림들을 치울 것이다.
너무 빽빽하면 아름답지 않으니 남아있는 모든 그림들 사이에는 적어도 D미터의 간격이 있게 만드려고 한다.
석표는 남아있는 그림의 가치 중 최소값이 최대가 되도록 하고 싶다.
만들 수 있는 최소 가치의 최대값은 얼마일까?
입력
다음과 같은 형태로 입력이 주어진다.
N M D
X_1 V_1
...
X_N V_N
1 <= M <= N <= 100,000
1 <= D <= 1,000,000
1 <= X_i <= 1,000,000,000
1 <= V_i <= 1,000,000,000
모든 그림의 위치는 서로 다르다.
N<=1000 인 경우를 해결하면 35%의 점수를 받을 수 있음이 보장된다.
출력
조건을 만족하도록 그림을 남길 수 없으면 -1을 출력하고,
존재한다면 가능한 최대의 최소 가치를 출력하라.
예제 #1
3 1 34
10 250
30 200
50 500
500
예제 #2
4 4 10
21 160
32 270
11 115
44 205
115
예제 #3
4 4 14
21 160
32 270
11 115
44 205
-1
예제 #4
6 3 4
4 2
5 2
2 1
9 2
1 1
7 2
1
출처
JOIG 2021
로그인해야 코드를 작성할 수 있어요.