R02193
K칸 복구 최장 거리
실버 II레이팅
의견: 0
설명
상점가에 \(N\)개의 점포가 일렬로 있으며, \(i\)번째 점포는 열려 있으면 \(1\), 닫혀 있으면 \(0\)으로 표시된다.
관리인은 닫힌 점포를 최대 \(K\)개까지 복구하여 열 수 있다. 복구를 적절히 하여 모두 열린 상태로 만들 수 있는 가장 긴 연속 점포 구간의 길이를 구하여라.
제약
\(1 \le N \le 100\,000\), \(0 \le K \le N\), \(a_i \in \{0,1\}\)
입력 형식
첫째 줄에 점포 수 \(N\)과 복구 가능 횟수 \(K\)가 주어진다.
둘째 줄에 \(N\)개의 상태 \(a_1, \dots, a_N\)(\(0\) 또는 \(1\))이 주어진다.
출력 형식
복구 후 모두 열린 상태가 되는 가장 긴 연속 구간의 길이를 출력한다.
서브태스크
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 30점 | \(1 \le N \le 400\) |
Subtask 2 | 70점 | 추가 제약이 없다. |
예제 1
입력
8 1
1 1 0 1 1 0 1 1
출력
5
설명
닫힌 칸 하나를 복구하면 \([1,1,0,1,1]\)처럼 길이 \(5\)의 구간을 만들 수 있다.
예제 2
입력
5 0
1 0 1 1 1
출력
3
설명
복구가 없으므로 이미 열린 칸의 최장 연속 구간 \([1,1,1]\)인 길이 \(3\)이다.
문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
K칸 복구 최장 거리
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
K칸 복구 최장 거리
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기