한 줄 행사 구역

문제

어느 주차장은 일렬로 놓인 주차 칸 일부를 골라 작은 행사를 열려고 한다. 주차 칸은 왼쪽부터 1번부터 N번까지 번호가 붙어 있다. 각 칸에는 차량이 정확히 한 대 있거나 아무 차량도 없다. 현재 상태는 길이가 N인 문자열 S로 주어지며, 왼쪽에서 i번째 문자가 0이면 i번 칸이 비어 있고 1이면 차량이 있다는 뜻이다. 행사 구역은 번호가 연속한 주차 칸을 하나 이상 선택하여 만든다. 선택한 구역 안에 있는 차량은 모두 별도의 임시 보관 장소로 옮겨야 한다. 임시 보관 장소의 공간은 충분하지만, 준비 시간 때문에 옮길 수 있는 차량은 전체를 합쳐 최대 K대다. 차량 한 대를 옮기는 데 드는 작업량은 어느 칸에 있든 같다. 구역 밖의 차량은 그대로 두며, 구역 밖의 빈칸을 행사 구역에 따로 덧붙일 수는 없다. 따라서 선택한 구역에 처음부터 있던 차량 수가 K 이하일 때만 그 구역을 사용할 수 있다. 비어 있던 칸과 차량을 옮겨 비운 칸은 모두 행사에 사용할 수 있으며, 구역의 크기는 선택한 주차 칸의 개수다. 차량을 반드시 K대 옮길 필요는 없고, 차량을 한 대도 옮기지 않는 선택도 허용한다. 관리자는 사용할 수 있는 구역 중 크기가 가장 큰 구역을 정하려고 한다. 크기가 같은 구역이 여러 개라면 시작 칸의 번호가 가장 작은 구역을 선택한다. 시작 칸과 크기가 정해지면 끝 칸도 하나로 정해진다. 선택한 구역의 크기와 양 끝 칸의 번호를 구하는 프로그램을 작성한다. 사용할 수 있는 칸이 하나도 없다면 구역을 만들지 않으며, 이 경우에는 정해진 특별한 값을 출력한다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 200,000이고 0 ≤ K ≤ N이다.
둘째 줄에 문자 0과 1로만 이루어진 길이 N의 문자열 S가 주어진다. S의 i번째 문자는 i번 주차 칸의 현재 상태다.

출력

선택한 구역의 크기 L, 시작 칸 번호 A, 끝 칸 번호 B를 공백으로 구분하여 한 줄에 출력한다. 사용할 수 있는 구역이 있다면 L = B - A + 1이며, 크기를 최대화하고 동점이면 A를 최소화해야 한다. 사용할 수 있는 구역이 하나도 없다면 0 0 0을 출력한다.

10 1
1100001101

5 2 6

5 0
00000

5 1 5

4 0
1111

0 0 0

출처: Devin.KR 자체 제작