#2893. 舞台

舞台

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

"星屑飘洒的舞台上,可人绽放的爱之花,99\red{99 }期生爱城华恋,我会令大家星光照耀 的!"

为了让大家星光闪耀,爱城华恋做起了舞台幕后灯光师的工作 2333333\red{2333333}。。。

舞台由 n\red{n }个位置组成,爱城华恋需要用灯光照亮整个舞台。每一个位置上有一盏灯, 分为大灯与小灯。

当一盏大灯被点亮,它可以照亮向左向右分别延伸 k\red{k }个位置,比如 k=1\red{k = 1 }时,它可 以照亮包括自身在内的三个位置(超出舞台范围部分无需考虑)。

当一盏小灯被点亮,它只能照亮自己的位置。

无论是大灯还是小灯,点亮第 i\red{i }个位置的灯光的花费为 i\red{i}

作为一名舞台少女,爱城华恋的幕后经验基本为零,她想让你帮助她寻找花费最低 的方式来照亮整个舞台。

输入格式

第一行两个整数 n,k\red{n, k,}表示舞台的大小以及大灯可以照亮的范围。

第二行一个由 0\red{0 }1\red{1 }组成的字符串,第 i\red{i }个字符为 1\red{1 }表示此处为大灯,0\red{0 }表示此处 为小灯。

输出格式

一个整数,照亮舞台所需的最小花费。

样例

输入样例1

7 1
0100010

输出样例1

12

输入样例2

5 3
00000

输出样例2

15

提示

对于 30%\red{30\% }的数据,满足 1\red{1 ≤} n\red{n ≤} 20\red{20}

对于所有数据,满足 1\red{1 ≤} n,k\red{n, k ≤} 105\red{10^5}

其中有 10%\red{10\% }的数据满足舞台上只有一个大灯。

20%\red{20\% }的数据满足舞台上有两个大灯。

国庆集训4

未参加
状态
已结束
规则
OI
题目
4
开始于
2022-10-2 14:00
结束于
2022-10-2 17:00
持续时间
3 小时
主持人
参赛人数
13