시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (추가 시간 없음) 512 MB 41 14 14 63.636%

문제

N개의 손가락을 가진 세빈이는 한 손만으로 모든 곡을 연주할 수 있는 최고의 피아니스트다.

세빈이의 두 인접한 손가락 사이의 거리는 K로 일정하다. 고로 i번째 손가락과 첫번째 손가락 사이의 거리를 Xi라고 한다면, Xi = (i-1)K가 성립한다(1 ≤ iN).

세빈이는 M개의 음으로 이루어진 곡을 연주하려 한다. 이때 각각의 음을 어떤 손가락으로 연주하는지에 따라 곡을 연주하는 것이 쉬워질 수도, 어려워질 수도 있다.

i번째 음의 음높이를 Pi라 하고, 이 음을 Fi번째 손가락으로 연주한다 하자. i번째 음과 이와 인접한 (i+1)번째 음을 연주할 때의 난이도는 |(Pi+1 - Pi) - (XFi+1 - XFi)|다.

곡의 난이도는 인접한 두 음을 연주할 때의 난이도의 최댓값으로 정의한다. 각각의 음을 어떤 손가락으로 연주할지 결정하여 곡의 난이도를 최소화하는 프로그램을 작성하시오.

입력

첫번째 줄에 세빈이의 손가락의 수와 곡을 이루는 음의 수를 나타내는 두 자연수 NM, 두 인접한 손가락 사이의 거리를 나타내는 자연수 K가 사이에 공백을 두고 주어진다.

두번째 줄에는 M개의 정수 P1, ···, PM이 사이에 공백을 두고 주어진다.

출력

첫번째 줄에 곡의 난이도의 최솟값을 출력한다.

제한

모든 입력 데이터는 다음 조건을 만족한다.

  • 1 ≤ N ≤ 2 × 105
  • 2 ≤ M ≤ 2 × 105
  • 1 ≤ K ≤ 109
  • XN ≤ 109
  • 1 ≤ Pi ≤ 109 (1 ≤ i ≤ M)

예제 입력 1

5 4 3
7 2 9 3

예제 출력 1

1

F1 = 3, F2 = 1, F3 = 3, F4 = 1.

출처

High School > 경기과학고등학교 > 나는코더다 2019 송년대회 G번

  • 문제를 만든 사람: sebinkim
  • 데이터를 만든 사람: yclock