Задача №115400. Качественный отдых
Прохор проходит стажировку продолжительностью \(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\) дополнительных выходных дней.
| Дополнительные ограничения | |||||
| Подзадача | Баллы | \(n\) | \(q\) | дополнительно | Необх. подзадачи |
| 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\) | – | – | У, 5 |
| 7 | 13 | – | – | В графике нет двух выходных подряд | 1, 2 |
| 8 | 11 | – | – | – | У, 1–7 |
В первом примере все три дня стажировки являются рабочими. Если взять менее двух отгулов, дней качественного отдыха получить невозможно. Для \(k_3=2\) или \(k_4=3\) можно выбрать отгулами первые \(k_j\) дней стажировки, и все они будут днями качественного отдыха.
Во втором примере один отгул выгодно взять во второй день стажировки, тогда первые три дня стажировки будут днями качественного отдыха.
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