dlaud5379   11달 전

(Kagi Translate로 번역한 텍스트를 다듬었습니다. 오역이 있으면 답글로 달아주세요. 감사합니다 🙇)

문제

잇창명은 IT 회사에서 n일 동안 인턴십을 진행하고 있다. 잇창명은 고객지원팀에서 근무하기 때문에 근무표가 비교적 복잡한 편이다.

잇창명은 정기 휴일 이외에도 원하는 근무일에 정해진 일수만큼 휴가를 사용할 수 있다.

휴일이 하루로 끝난다면 제대로 쉴 수 없기 때문에, 잇창명은 2일 이상의 연휴만을 중요하게 생각한다.

q개의 휴가 일수가 질의로 주어질 때, 정해진 근무표를 바탕으로 연휴 일수를 최대화하는 프로그램을 작성하여라.

입력

첫째 줄에 n과 q가 공백으로 구분되어 주어진다. (1 ≤ n ≤ 100,000, 1 ≤ q ≤ n + 1)

둘째 줄에 잇창명의 근무표가 주어진다. 근무표는 숫자 '0'과 '1'로만 이루어진 길이 n의 문자열로, i번째 문자가 '0'일 경우 i번째 날이 근무일, '1'일 경우 휴일이라는 의미이다.

셋째 줄부터 q줄에 걸쳐 질의가 주어진다. i번째 질의는 휴가 일수를 의미하는 한 개의 정수 ki (0 ≤ ki ≤ n)로 이루어져 있다. 휴가 일수는 근무표의 근무일을 초과하지 않는다.

출력

q줄에 걸쳐 답을 출력한다. i번째 줄에는 휴가 일수가 ki일 때 최대 연휴 일수를 한 줄로 출력한다.

서브태스크

번호배점제한
16근무표의 모든 날이 근무일이다.
211근무표에 휴일과 근무일이 교대로 주어진다. 첫째 날은 휴일이다.
312q = 1, k1 = 0
419q = 1, k1 = 1
511n ≤ 15
617n ≤ 1,000
713근무표에 휴일이 연속으로 주어지지 않는다.
811추가 제한 조건이 없다.

노트

예제 입력 1에서는 근무표의 모든 날이 근무일이다. 휴가가 2일 미만일 경우 연휴를 만들 수 없다. k3 = 2이거나 k4 = 3의 경우에는 인턴십 기간 중 처음 kj일 동안 휴가를 쓰면 모든 휴가일이 연휴가 된다.

예제 입력 2에서는 둘째 날에 휴가를 쓰면 인턴십 기간의 처음 3일이 연휴가 된다.

댓글을 작성하려면 로그인해야 합니다.