시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB (추가 메모리 없음)21813011164.912%

문제

연두는 $N$개의 통에 초콜릿을 담아서, 초콜릿의 개수가 오름차순이 되도록 일렬로 배열해 놓는다. 즉, ($1$번째 통의 초콜릿의 개수) $\le$ ($2$번째 통의 초콜릿의 개수) $\le \dots \le$ ($N$번째 통의 초콜릿의 개수)이다. 

효원이는 매일 조금씩 연두의 초콜릿을 몰래 뺏어 먹을 계획을 세우는 중이다. 연두는 매우 눈치가 없기 때문에, 하루에 한 번 다음의 전략을 사용해서 초콜릿을 먹는다면 절대 눈치채지 못할 것이다.

  1. $K<i$인 $i$를 골라, $i-K$번째 통에 있는 초콜릿의 개수와 똑같아질 때까지 $i$번째 통에서 초콜릿을 꺼내 먹는다.
  2. 그 후 통을 재정렬한다. 즉, 초콜릿의 개수가 오름차순이 되도록 통을 재배치 한다.

효원이는 연두가 눈치채지 못하는 선에서 최대한 많이, 그리고 최대한 빨리 초콜릿을 먹어 치우고 싶다. 과연 몇 개나 먹을 수 있을까?

입력

첫 번째 줄에 통의 개수 $N$과 $K$가 주어진다. ($1 \le K < N \le 2\,000$)

두 번째 줄에 초기에 $i$번째 통에 들어있는 초콜릿의 개수 $a_1, a_2, \dots, a_N$이 주어진다. ($1 \le a_1 \le a_2 \le \dots \le a_N \le 2\,000$)

출력

연두에게 들키지 않으면서 먹을 수 있는 초콜릿의 최대 개수와, 그 개수의 초콜릿을 먹기 위해 필요한 최소 날짜를 출력한다.

예제 입력 1

4 2
1 2 2 3

예제 출력 1

4 3
  • $1$일 : $3$번째 통을 고른다 ($[1, 2, \underline{2}, 3] \rightarrow [1, 2, \underline{1}, 3] $). 그 후 통을 재정렬 한다 ($[1, 1, 2, 3]$).
  • $2$일 : $4$번째 통을 고른다 ($[1, 1, 2, \underline{3}] \rightarrow [1, 1, 2, \underline{1}] $). 그 후 통을 재정렬 한다 ($[1, 1, 1, 2]$).
  • $3$일 : $4$번째 통을 고른다 ($[1, 1, 1, \underline{2}] \rightarrow [1, 1, 1, \underline{1}]$). 통은 이미 정렬되어 있다.

예제 입력 2

2 1
5 5

예제 출력 2

0 0

출처

University > 홍익대학교 > 2021 홍익대학교 프로그래밍 경진대회 C번