꽃다발 납품일
실버 II의견: 0
화훼 농장의 화단에 꽃 \(N\)송이가 일렬로 심어져 있고, \(i\)번째 꽃은 \(b_i\)일째 되는 날 핀다. 한 번 핀 꽃은 지지 않는다.
꽃다발 하나를 만들려면 화단에서 서로 이웃한, 이미 핀 꽃 정확히 \(K\)송이를 잘라야 한다. 각 꽃은 최대 한 다발에만 쓸 수 있다.
꽃다발 \(M\)개를 납품할 수 있는 가장 빠른 날을 구하여라. 모든 꽃이 피어도 만들 수 없다면 \(-1\)을 출력한다.
- \(1 \le N \le 100\,000\)
- \(1 \le M, K \le N\)
- \(1 \le b_i \le 10^9\)
첫째 줄에 꽃의 수 \(N\), 필요한 다발 수 \(M\), 다발 하나에 드는 꽃의 수 \(K\)가 공백으로 구분되어 주어진다.
둘째 줄에 개화일 \(b_1, b_2, \dots, b_N\)이 화단 순서대로 주어진다.
다발 \(M\)개를 만들 수 있는 가장 빠른 날을 출력한다. 불가능하면 \(-1\)을 출력한다.
5 1 3
5 5 1 2 3
3
\(3\)일째에는 \(3, 4, 5\)번째 꽃이 피어 이웃한 \(3\)송이로 꽃다발 하나를 만들 수 있다. \(2\)일째에는 이웃하여 핀 꽃이 \(2\)송이뿐이다.
3 2 2
1 2 3
-1
꽃 \(3\)송이로는 \(2\)송이짜리 다발 \(2\)개를 만들 수 없으므로 \(-1\)을 출력한다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
꽃다발 납품일
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
꽃다발 납품일