oj.uz

문제 보기 - 격자 보존하기 (GA9_preserve)

격자 보존하기 Batch 컴파일 명령

시간 제한 메모리 제한 제출 횟수 통과한 사람 수 비율
1000 ms 32 MiB 72 23 31.94%

승현이는 1 × n 크기의 격자판을 가지고 있습니다. 각 칸에는 1 이상 n 이하의 자연수 번호가 왼쪽에서부터 차례대로 붙어있습니다. 이 중 k개의 칸에는 말이 하나씩 놓여 있는데, 이 말들은 격자들을 좋아해서, 도달 가능한 모든 격자판을 방문합니다. 말들이 자신의 격자판을 더럽히는 것을 보고만 있을 수 없었던 승현이는 d개의 칸막이를 구매했습니다. 각 칸막이는 인접한 두 격자가 만나는 선분 위에 놓을 수 있으며, 말들은 칸막이를 지나갈 수 없습니다.

위 그림에서, 지금 5번 격자에 있는 말은 3번, 4번, 5번 격자를 모두 방문하고, 8번 격자에 있는 말은 6번, 7번, 8번 격자를 모두 방문합니다. 보존되는 격자는 1번 격자와 2번 격자뿐입니다.

승현이는 d개의 칸막이들을 적절히 배치하여 어떤 말도 방문하지 않은 격자의 수를 최대화하려고 합니다. 하지만 그 방법은 잘 모르겠다고 합니다. 승현이를 도와 보존할 수 있는 최대 격자의 수를 구하는 프로그램을 작성하세요.

입력 형식

첫 번째 줄에 격자판의 크기 n, 말의 수 k, 칸막이의 수 d가 공백을 사이로 두고 주어집니다.

두 번째 줄에는 k개의 정수 p1, p2, ..., pk가 공백을 사이로 두고 주어집니다. 이 중 i (1 ≤ i ≤ k)번째 정수 pi는 i번 말이 위치한 칸의 번호를 나타냅니다.

출력 형식

승현이가 d개의 칸막이들을 잘 설치하여 보존할 수 있는 격자의 수의 최댓값을 출력합니다.

제약 조건

  • 2 ≤ n ≤ 109
  • 1 ≤ k ≤ min(105, n)
  • 1 ≤ d ≤ n - 1
  • 1 ≤ p1 < p2 < ... < pk - 1 < pk ≤ n

부분문제

부분문제 점수 n k d
1 9 ≤ 20 ≤ n  ≤ n - 1
2 17 ≤ 105 = 3 = 3
3 22 ≤ 106 ≤ 103 ≤ 102
4 17 ≤ 109 ≤ 105 ≤ 103
5 35 ≤ 109 ≤ 105 ≤ n - 1

예제

입력 예시 출력 예시
15 4 3
3 5 10 11		8
출처