[R69C]这是一个01串题4 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定一个长度为 $n$ 的 01 串 $s$ 和一个整数 $k$，你需要从这个 01 串中选出 $2$ 个下标 $i,j$，求满足以下条件的 $(i,j)$ 的个数：

• $i < j$
• $s_i = 0, s_j = 1$
• $j - i \le k$

格式

输入格式

第一行包含两个整数 $n$ 和 $k$，具体含义见题目描述。

第二行包含一个长度为 $n$ 的 01 串 $s$。

输出格式

输出一个整数，表示满足条件的二元组个数。

样例

样例输入 #1

5 2
00101

样例输出 #1

3

样例解释 #1

满足条件的数对如下：

• $(1,3)$
• $(2,3)$
• $(4,5)$

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$
$1$	$60$	$5000$
$2$	$40$	$2\times 10^5$

对于 $100\%$ 的数据，满足 $1 \le n \le 2 \times 10^5$，$1 \le k \le n$。