시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 203 | 74 | 62 | 35.632% |
OJ시는 직선 형태의 가로수길에 총 N개의 가로등을 설치했다. 각 가로등의 위치는 지하철역을 기준으로 -1,000,000,000 이상 1,000,000,000 이하의 정수로 나타낼 수 있다. 한편, 모든 가로등은 자신과 L만큼 먼 곳까지 빛을 밝힐 수 있다. 예를 들어, 좌표가 5인 가로등이 2만큼 먼 곳까지 빛을 밝힐 수 있다면 좌표가 3~7인 곳을 밝힐 수 있다.
요즘 들어, OJ시에 전력난이 지속되어 자주 정전이 난다. 정전이 나면 가로수길이 완전히 암흑에 둘러싸이기 때문에 치안에 악영향을 끼친다. 따라서 OJ시에서 N개의 가로등들 중 일부를 비상용으로 전환해서 정전 시에만 켜지게 할 것이다.
평소의 조명 상태와 정전 시의 조명 상태가 균일하게 이루어져야 언제든지 시민들이 편하게 가로수길을 드나들 수 있다. 이에 따라 OJ시는 어떤 경우에도 항상 빛이 도달하는 지점의 총 길이를 최대화시키려고 한다. OJ시를 도와 무슨 가로등을 비상용으로 바꿀지 구하는 프로그램을 작성하여라.
첫 번째 줄에는 가로등의 수 N과 가로등의 조도 L이 주어진다.
두 번째 줄에는 N개의 가로등의 좌표가 공백을 사이로 두고 차례대로 주어진다.
가로등 중에 몇 개를 비상용으로 전환했을 때, 평상시와 비상시에 모두 빛의 영향을 받는 영역의 길이의 최댓값을 출력한다.
6 3 -6 -2 1 3 8 15
9
2, 4번째 가로등을 비상용으로 전환하면 된다.