D-切割 01 串 2.0_牛客小白月赛98

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 给定一个长度为 $n$ 的 $01$ 串 $s$ 。一次切割操作如下：

$\hspace{23pt}\bullet\,$ 选择一个长度 $\ge 2$ 的子串，将其分成两个非空连续子串 $a$ （左）和 $b$ （右）；
$\hspace{23pt}\bullet\,$ 记 $a$ 中字符 $0$ 的出现次数为 $C_0$ ， $b$ 中字符 $1$ 的出现次数为 $C_1$ ；
$\hspace{23pt}\bullet\,$ 仅当 $L\leqq |C_0-C_1|\leqq R$ 时，此次切割被视为合法。

$\hspace{15pt}$ 每次合法切割产生的两个子串都可以继续被独立切割（若长度 $\ge 2$ 且满足切割条件）。问在最优策略下，最多可以执行多少次切割？

输入描述:

第一行输入三个整数 ——字符串长度与参数限制。

第二行输入一个长度为  的  串 。

输出描述:

输出一个整数，表示最多能执行的切割次数。

示例1

输入

复制

6 2 3
011011

输出

复制

说明

其中一种切割次数最多的切法如下：
第一次切割可以切：，然后选择  这个串继续做切割。
第二次切割可以切：，然后选择  这个串继续做切割。
第三次切割可以切：。