#ABC124D. Handstand

Handstand

题目描述

NN people are arranged in a row from left to right.

You are given a string SS of length NN consisting of 0 and 1, and a positive integer KK.

The ii-th person from the left is standing on feet if the ii-th character of SS is 0, and standing on hands if that character is 1.

You will give the following direction at most KK times (possibly zero):

Direction: Choose integers ll and rr satisfying 1lrN1 \leq l \leq r \leq N, and flip the ll-th, (l+1)(l+1)-th, ......, and rr-th persons. That is, for each i=l,l+1,...,ri = l, l+1, ..., r, the ii-th person from the left now stands on hands if he/she was standing on feet, and stands on feet if he/she was standing on hands.

Find the maximum possible number of consecutive people standing on hands after at most KK directions.

NN 人从左到右排成一排。

给你一个长度为 NN 的字符串 SS ,由 01 以及一个正整数 KK 组成。

如果 SSii 第三个字符是0,那么从左边开始的 ii 第三个人是用脚站立的;如果该字符是1,那么从左边开始的 ii 第三个人是用手站立的。

您最多可以发出 KK 次(可能为零)以下指令:

方向:选择满足 1lrN1 \leq l \leq r \leq N 的整数 llrr ,并翻转第 ll 个、第 (l+1)(l+1) 个、 ...... 和第 rr 个的人。也就是说,对于每一个 i=l,l+1,...,ri = l, l+1, ..., r ,左边的 ii -3人现在如果是用脚站立,就用手站立,如果是用手站立,就用脚站立。

求最多经过 KK 个方向后,个连续人双手站立的最大可能人数。

输入格式

输入内容按以下格式标准输入:

NN KK
SS

输出格式

打印最多经过 KK 个方向后,连续双手站立的最大可能人数。

样例 #1

样例输入 #1

5 1
00010

样例输出 #1

4

样例 #2

样例输入 #2

14 2
11101010110011

样例输出 #2

8

样例 #3

样例输入 #3

1 1
1

样例输出 #3

1

说明

数据规模与约定

  • NN 是满足 1N1051 \leq N \leq 10^5 的整数。
  • KK 是满足 1K1051 \leq K \leq 10^5 的整数。
  • 字符串 SS 的长度为 NN
  • 字符串 SS 中的每个字符都是 "0 "或 "1"。

样例 11 解释

我们可以通过发出以下指令,让连续四个人手拉手站立,这就是最大结果:

  • 给出带有 l=1,r=3l = 1, r = 3 的方向,从左侧翻转第一、第二和第三个人。

样例 33 解释

无需说明。