| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 52 | 15 | 15 | 36.585% |
Прохор проходит стажировку продолжительностью $n$ календарных дней в ИТ-компании. Прохор стажируется в службе поддержки, поэтому у него сложный график рабочих и выходных дней на время стажировки.
Кроме выходных, у Прохора есть некоторое количество отгулов --- дополнительных выходных дней, которые он может взять в любые рабочие дни.
За один выходной день Прохор качественно отдохнуть не сможет, поэтому он считает днями качественного отдыха только те выходные дни, которые входят в последовательность из идущих подряд двух или более выходных дней.
Вам даны $q$ запросов --- различных значений количества отгулов, которые может взять Прохор. Ваша задача --- по заданному графику рабочих и выходных дней стажировки определить для каждого запроса, какое максимальное количество дней качественного отдыха за время стажировки может получить Прохор.
Первая строка входных данных содержит два целых числа $n$ и $q$ ($1 \le n \le 100\,000$, $1 \le q \le n+1$).
Следующая строка содержит строку $s$ длины $n$, состоящую из символов <<0>> и <<1>> --- график стажировки. В этой строке символом <<0>> обозначается рабочий день, а символом <<1>> --- выходной.
В следующих $q$ строках находятся $q$ целых чисел $k_i$ ($0 \leq k_i \leq n$) --- количество отгулов в $i$-м запросе. Гарантируется, что каждое значение $k_i$ не превосходит количества рабочих дней в графике стажировки.
Выведите $q$ целых чисел --- для каждого значения $k_i$ определите наибольшее количество качественных дней отдыха, которое может получить Прохор за время стажировки, выбрав $k_i$ дополнительных выходных дней.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 6 | Все дни графика --- рабочие |
| 2 | 11 | Выходные и рабочие дни чередуются, первый день стажировки --- выходной |
| 3 | 12 | $q = 1$, $k_1 = 0$ |
| 4 | 19 | $q = 1$, $k_1 = 1$ |
| 5 | 11 | $n \le 15$ |
| 6 | 17 | $n \le 1000$ |
| 7 | 13 | В графике нет двух выходных подряд |
| 8 | 11 |
3 4 000 0 1 2 3
0 0 2 3
4 3 1010 0 1 2
0 3 4
11 6 11010101001 5 2 0 1 4 3
11 7 2 5 10 9
В первом примере все три дня стажировки являются рабочими. Если взять менее двух отгулов, дней качественного отдыха получить невозможно. Для $k_3=2$ или $k_4=3$ можно выбрать отгулами первые $k_j$ дней стажировки, и все они будут днями качественного отдыха.
Во втором примере один отгул выгодно взять во второй день стажировки, тогда первые три дня стажировки будут днями качественного отдыха.