시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB (추가 메모리 없음) | 589 | 343 | 284 | 58.799% |
연두는 $N$개의 통에 초콜릿을 담아서, 초콜릿의 개수가 오름차순이 되도록 일렬로 배열해 놓는다. 즉, ($1$번째 통의 초콜릿의 개수) $\le$ ($2$번째 통의 초콜릿의 개수) $\le \dots \le$ ($N$번째 통의 초콜릿의 개수)이다.
효원이는 매일 조금씩 연두의 초콜릿을 몰래 뺏어 먹을 계획을 세우는 중이다. 연두는 매우 눈치가 없기 때문에, 하루에 한 번 다음의 전략을 사용해서 초콜릿을 먹는다면 절대 눈치채지 못할 것이다.
효원이는 연두가 눈치채지 못하는 선에서 최대한 많이, 그리고 최대한 빨리 초콜릿을 먹어 치우고 싶다. 과연 몇 개나 먹을 수 있을까?
첫 번째 줄에 통의 개수 $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$)
연두에게 들키지 않으면서 먹을 수 있는 초콜릿의 최대 개수와, 그 개수의 초콜릿을 먹기 위해 필요한 최소 날짜를 출력한다.
4 2 1 2 2 3
4 3
2 1 5 5
0 0
University > 홍익대학교 > 2021 홍익대학교 프로그래밍 경진대회 C번