P12505 「ROI 2025 Day2」充实的假期

**译自 [ROI 2025](https://neerc.ifmo.ru/school/archive/2024-2025.html) Day2 T1.** ***[Качественный отдых](https://neerc.ifmo.ru/school/archive/2024-2025/ru-olymp-roi-2025-day2.pdf)*** 小明正在一家 IT 公司进行为期 $n$ 天的实习，担任技术支持的角色。他的实习日程安排颇为复杂，工作日和休息日交织在一起。除了固定的休息日，小明还有一些调休日——他可以选择在任意工作日额外休息一天。 不过，小明觉得单独一天的休息远远不够，只有连续两天或以上的休息日才能让他真正放松，称之为充实休假日。 你会收到 $q$ 个关于调休日数量的询问，每个询问对应一个不同的调休天数。你的任务是根据小明的实习日程，计算出在每种调休天数下，小明最多能获得多少个充实休假日。

第一行包含两个整数 $n$ 和 $q$ $(1 \le n \le 100\,000, 1 \le q \le n+1)$，分别表示实习天数和询问数量。 第二行包含一个长度为 $n$ 的字符串 $s$，由字符 `0` 和 `1` 组成，表示实习日程。其中，`0` 表示工作日，`1` 表示休息日。 接下来的 $q$ 行，每行包含一个整数 $k_i$ $(0 \leq k_i \leq n)$，表示第 $i$ 个询问中可用的调休天数。保证每个 $k_i$ 不超过日程中的工作日总数。

输出 $q$ 个整数，分别表示在每个 $k_i$ 调休天数下，小明通过选择 $k_i$ 个额外休息日，最多能获得的充实休假日数量。

### 样例解释 1 在第一个样例中，实习的 $3$ 天全是工作日。如果调休少于 $2$ 天，无法获得充实休假日。对于 $k_3 = 2$ 或 $k_4 = 3$，可以选择前 $k_j$ 天作为调休日，这些天都将成为充实休假日。 ### 样例解释 2 在第二个样例中，最优策略是将调休日安排在第二天，这样前三天都将成为充实休假日。 --- 详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。 | 子任务 | 分值 | 附加限制 | | :-: | :-: | :-: | |$0$|$0$|样例|| | $1$ | $6$ | 所有日程均为工作日 | | | $2$ | $11$ | 工作日与休息日交替，首日为休息日 | | | $3$ | $12$ | $q = 1$，$k_1 = 0$ | | | $4$ | $19$ | $q = 1$，$k_1 = 1$ | | | $5$ | $11$ | $n \le 15$ | $0$ | | $6$ | $17$ | $n \le 1000$ | $0,5$ | | $7$ | $13$ | 日程中无连续休息日 | $1,2$ | | $8$ | $11$ | 无附加限制 | $0,1-7$ |