Problem:


Score : 400 points

Problem Statement

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

You are given a string S of length N consisting of 0 and 1, and a positive integer K.

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

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

Direction: Choose integers l and r satisfying 1 \leq l \leq r \leq N, and flip the l-th, (l+1)-th, ..., and r-th persons. That is, for each i = l, l+1, ..., r, the i-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 K directions.

Constraints

N is an integer satisfying 1 \leq N \leq 10^5.

K is an integer satisfying 1 \leq K \leq 10^5.

The length of the string S is N.

Each character of the string S is 0 or 1.

Input

Input is given from Standard Input in the following format:

N K
S

Output

Print the maximum possible number of consecutive people standing on hands after at most K directions.

Sample Input 1

5 1
00010

Sample Output 1

4

We can have four consecutive people standing on hands, which is the maximum result, by giving the following direction:

Give the direction with l = 1, r = 3, which flips the first, second and third persons from the left.

Sample Input 2

14 2
11101010110011

Sample Output 2

8

Sample Input 3

1 1
1

Sample Output 3

1

No directions are necessary.



Sample input:
5 1
00010


Sample output:
4

Submission status: Accepted

Solution code:
from sys import exit
N,K = [int(n) for n in input().split()]
# N = int(input())
# a = [int(input()) for _ in range(N)]
S = str(input())
L = len(S)
lis = []
if(S[0] == "0"):#偶数Indexがブリッジ
    lis.append(0)
tmp = S[0]

for i in range(1,L):
    if(S[i]!=S[i-1]):
        lis.append(len(tmp))
        tmp =S[i]
    else:
        tmp+=S[i]
lis.append(len(tmp))
#0で終わっていたら最後に１が0個であるとする
if("0" in tmp):
    lis.append(0)
# print(lis)

#累積和をとる
L = len(lis)
# print(L)
asum = [0]*(L+1)
asum[0] = 0
for i in range(1,L+1):
    asum[i] = asum[i-1] + lis[i-1]
# print(asum)

#尺をとる
l = 0
ans = max(lis) if l+2*K+1 < L+1 else sum(lis)
for r in range(l+2*K+1 , L+1,2):
    # print(l,r)
    # print(asum[r] - asum[l])
    ans = max(asum[r] - asum[l],ans)
    l+=2
print(ans)

# 14 2
# 11101010110011
# 10 1
# 0000000001

Submission status: Accepted

Solution code:
N,K = map(int, input().strip().split(' '))
S = input().strip()
l,r,now_max,now_zeros = 0,0,1,0
for r in range(1,N):
  if S[r-1] == '0':
    if S[r] == '0':
      continue
    else:
      now_zeros += 1
  else:
    if S[r] == '0':
      if now_zeros < K:
        continue
      else:
        now_max = max(r-l, now_max)
        now_zeros -= 1
        for _ in range(l,r):
          l += 1
          if S[l-1:l+1] == '01':
            break
    else:
      continue
now_max = max(r-l+1, now_max)
print(now_max)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import itertools

def solve(N: int, K: int, S: str):
    border = []
    prev = False
    first = S[0]
    for i, c in enumerate(S):
        if c != prev:
            border.append(i)
            prev = c
    border.append(N)
    length = len(border)
    if first == '1':
        size = (length - 1) // 2
    else:
        size = length // 2

    if K >= size:
        print(border[-1] - border[0])
        return
    
    res = 0
    for i in range(size-K+1):
        if first == '1': 
            res = max([res, border[min([2*i + 2*K + 1, length-1])] - border[2*i]])
        else: 
            res = max([res, border[min([2*i + 2*K, length-1])] - border[max([2*i - 1, 0])]])
    print(res)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, K, S)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K=(int(i) for i in input().split())
S =input()
if S[0]=="0" :biti=0
else:biti=1
if S[-1]=="0" :bitf=0
else:bitf=1
a=[0]
for i in range(0,len(S)-1):
  if S[i]!=S[i+1]:
    a.append(i+1)
a.append(len(S))

def func():
  maxanswer=0
  for i in range(0,len(a)-2*K-1*bitf):
    if biti==0 and i==0:
      if maxanswer<a[i+K*2]-a[i]:maxanswer=a[i+K*2]-a[i]
    elif bitf==0 and i==len(a)-2*K-1:
      if maxanswer<a[i+K*2]-a[i]:maxanswer=a[i+K*2]-a[i]
    elif maxanswer<a[i+K*2+((i%2)^(biti))]-a[i+((i%2)^(not biti))]:maxanswer=a[i+K*2+((i%2)^(biti))]-a[i+((i%2)^(not biti))]
  print(maxanswer)


if biti==bitf:
  if biti==0:
    if len(a)<=(K*2-1):print(a[-1])
    else:
      func()
  else:
    if len(a)<=(K*2+1):print(a[-1])
    else:
      func()
else:
  if len(a)<=K*2:print(a[-1])
  else:
    func()

Submission status: Accepted

Solution code:
N, K = [int(a) for a in input().split()]
S = "1" + str(input()) + "0"
ans = 0
cnt = 1 if S[1] == "0" else 0
num = 0
l, r = (1, 1)
while r <= N:
    while cnt <= K and r<=N:
        if S[r]=="1" and S[r+1]=="0":
            cnt+=1
        num += 1
        r+=1
    ans = max(num, ans)
    while cnt > K and l<=N:
        num -= 1
        l+=1
        if S[l]=="1" and S[l-1]=="0":
            cnt -= 1
print(ans)

Submission status: Accepted

Solution code:
# input
n, k = list(map(int, input().split()))
s = input()

# solve

##. number of consecutive 0 groups and 1 groups
##. ex:
##.  s = '11101010110011'
##.       0: 0, 0, 0, 00
##.       1: 111, 1, 1, 11, 11
##.  zeros = [1, 1, 1, 2]
##.  ones = [3, 1, 1, 2, 2]
##.   (always count the edges of s as 1)
zeros = []
ones = []
_c = '1'
count = 0
for c in s:
	if _c == c:
		count += 1
	else:
		if _c == '0':
			zeros.append(count)
		else:
			ones.append(count)
		_c = c
		count = 1

if c == '0':
	zeros.append(count)
	ones.append(0)
else:
	ones.append(count)

if len(zeros) <= k:
	## flip all 0's
	ans = len(s)
else:
  ## flip k consecutive zero groups
  ans = 0

  i = 0
  _ans = sum(zeros[i:i+k]) + sum(ones[i:i+k+1])
  ans = _ans

  i = 1
  while i + k <= len(zeros):
#	  _ans = sum(zeros[i:i+k]) + sum(ones[i:i+k+1])
	  _ans += zeros[i+k-1] - zeros[i-1] + ones[i+k] - ones[i-1]
	  ans = max(ans, _ans)
	  i += 1

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()

nums = []
now = 1
seq_count = 0
for char in S:
    if char == str(now):
        seq_count += 1
    else:
        now = 1 - now
        nums.append(seq_count)
        seq_count = 1

nums.append(seq_count)

if len(nums) % 2 == 0:
    nums.append(0)

sums = [0] * (len(nums) + 1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]

ans = 0
for i in range(1, len(sums), 2):
    left = i - 1
    right = min(i + 2 * K, len(sums) - 1)
    ans = max(ans, sums[right] - sums[left])
print(ans)

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
S = input()

D = []
count = 0
mode = 1
if S[0] == "0":
    D.append(0)
    mode = 0

for i in range(N):
    if int(S[i]) == mode:
        count += 1
    else:
        D.append(count)
        count = 1
        mode = 1 - mode
    if i == N-1:
        D.append(count)

if S[-1] == "0":
    D.append(0)
lk = int((len(D)-1)/2)
if K > lk:
    K = lk
ans = sum(D[:(2*K+1)])
sumd = ans
for i in range(int((len(D)-2*K-1)/2)):
    sumd += D[2*K+2*i+1]+D[2*K+2*i+2]-D[2*i]-D[2*i+1]
    if sumd > ans:
        ans = sumd

print(ans)

Submission status: Accepted

Solution code:
N , K = map(int,input().split())
S = input()
L = []
flag = int(S[0])
for x in S:
    L.append(x)
cnt = 1
C = []
for i in range(len(L)):
    try:
        if L[i] == L[i+1]:
            cnt += 1
        else:
            C.append(cnt)
            cnt = 1
    except:
        pass
C.append(cnt)
ans = 0
from itertools import accumulate
accumulated =  [0]+list(accumulate(C))
ans = 0
A = 0
if flag == 0:
    if len(C) % 2 == 0:
        k = min(K,len(C)//2)
    else:
        k = min(K,len(C)//2+1)
else:
    k = min(K,len(C)//2)
for i in range(len(C)):
    try:
        if (flag + i) % 2 == 0:
            A =max(A, accumulated[i+2*k-1] - accumulated[i])
            ans = accumulated[i+2*k] - accumulated[i]
        else:
            A =max(A, accumulated[i+2*k-1] - accumulated[i])
            A =max(A, accumulated[i+2*k] - accumulated[i])
            ans = accumulated[i+2*k+1] - accumulated[i]
        A = max(ans,A)
    except:
        pass
print(A)

Submission status: Accepted

Solution code:
N,K= map(int, input().split())
S=[int(x) for x in list(str(input()))]

nums=list()
ds={0:1,1:0}
now=1
cnt=0
for i in S:
    if i==now:
        cnt=cnt+1
    else:
        nums.append(cnt)
        now=ds[now]
        cnt=1

if cnt!=0:
    nums.append(cnt)

if len(nums)%2==0:
    nums.append(0)

Add=2*K+1
ans=0

sum=[0]*(len(nums)+1)
for i in range(len(nums)):
    sum[i+1]=sum[i]+nums[i]

for i in range(0,len(nums),2):
    
    left=i
    right=min(i+Add,len(nums))

    tmp=sum[right]-sum[left]
    ans=max(ans,tmp)

print(ans)

Submission status: Accepted

Solution code:
N,K= map(int, input().split())
S=[int(x) for x in list(str(input()))]

nums=list()
ds={0:1,1:0}
now=1
cnt=0
for i in S:
    if i==now:
        cnt=cnt+1
    else:
        nums.append(cnt)
        now=ds[now]
        cnt=1

if cnt!=0:
    nums.append(cnt)

if len(nums)%2==0:
    nums.append(0)

Add=2*K+1
ans=0
left=0
right=0
tmp=0
for i in range(0,len(nums),2):
    
    nextleft=i
    nextright=min(i+Add,len(nums))
    while nextleft>left:
        tmp=tmp-nums[left]
        left+=1

    while nextright>right:
        tmp=tmp+nums[right]
        right+=1
        

    ans=max(ans,tmp)

print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
s = list(map(int,input()))
s.append(2)
start = s[0]
number = 1
choku = []
saka = [0]
for i in range(N):
    if s[i] == s[i+1]:
        number += 1
    else:
        if s[i] == 0:
            choku.append(number)
            number = 1
        else:
            saka.append(number)
            number = 1
choku.append(0)
saka.append(0)
while(1):
    max_align = 0
    m = len(choku)
    n = len(saka)
    if m <= K:
        print(N)
        break
    if start == 0: #最初が直立の場合
        aligns = [sum(choku[0:K]) + sum(saka[0:K+1])]
        for i in range(m-K-1):
            aligns.append(aligns[i] -choku[i]-saka[i] + choku[i+K] + saka[i+K+1])
        print(max(aligns))
    else:
        aligns = [sum(choku[0:K]) + sum(saka[1:K+2])]
        for i in range(m-K-1):
            aligns.append(aligns[i] -choku[i]-saka[i+1] + choku[i+K] + saka[i+K+2])
        print(max(aligns))
    break

Submission status: Accepted

Solution code:
n,k = list(map(int, input().split()))
s = input()
if (s.find('0') < 0) or (s.find('1') < 0):
	print(len(s))
	quit()
else:
	s += '0' if s[n-1] == '1' else '1'
c = []

j = 0
for i in range(1, n+1):
	if s[i-1] == s[i]:
		j += 1
	else:
		c.append([s[i-1], j+1])
		j = 0

for i in range(1, len(c)):
	c[i][1] += c[i-1][1]

if 2*k >= len(c):
	print(c[-1][1])
	quit()
else:
	p = 0
	res = 0
	if c[0][0] == '0':
		res = c[1][1] if k == 1 else c[2*k-1][1]
		p += 1
	else:
		res = c[2][1] if k == 1 else c[2*k][1]
		p += 2

	while p+2*k < len(c):
		res = max(res, c[p+2*k][1] - c[p-1][1])
		p += 2

	res = max(res, c[-1][1] - c[(len(c)-1) - 2*k][1]) if c[-1][0] == '0' else max(res, c[-1][1] - c[(len(c)-1) - (2*k+1)][1])

	print(res)
	quit()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S = input()

hm_1 = [0] * N
hm_2 = [0] * N

for i in range(N-1,-1,-1):
	if i == N-1:
		if S[i] == '1':
			hm_1[i] = 1
	else:
		if S[i] == '0':
			hm_1[i] = 0
		else:
			hm_1[i] = hm_1[i+1] + 1
		
for i in range(N-1,-1,-1):
	if i == N-1:
		if S[i] == '0':
			hm_2[i] = 1
	else:
		if S[i] == '1':
			hm_2[i] = 0
		else:
			hm_2[i] = hm_2[i+1] + 1
#print (hm_1)
#print (hm_2)


rl = []
# run length 
# 1 - 0 - 1 - 0 - 1 - ...
i = 0
if hm_1[i] == 0:
	rl.append(0)
while i < N :
	if hm_1[i] != 0:
		rl.append(hm_1[i])
		i += hm_1[i]
	else:
		rl.append(hm_2[i])
		i += hm_2[i]

#print (rl)
# rl: index==even -> '1', index==odd -> '0'
# s : sum list
#rl.append(0)
s = [0] * (len(rl) + 1)


for j in range(len(rl)):
	s[j+1] = s[j] + rl[j]
#print (s)

ans = 0
for ra in range(0,len(s),2):
	tmp = 0
	right = min(ra + 2 * K + 1, len(s)-1)
	tmp = s[right] - s[ra]
	ans = max(tmp,ans)

print (ans)

Submission status: Accepted

Solution code:
n, k = [int(i) for i in input().split()]
s = [0,1] + [int(i) for i in list(input())] + [1,0]
down = [i for i in range(n+3) if s[i] == 1 and s[i+1] == 0]
up = [i for i in range(n+3) if s[i] == 0 and s[i+1] == 1]
#print(s)
#print(down)
#print(up)
ans = 1
if k >= len(up):
  ans = n
else:
  if down[k] - up[0] - 1 > ans:
    ans = down[k] - up[0] - 1
  for i in range(1,len(up)-k-1):
    if down[i + k] - up[i] > ans:
      ans = down[i + k] - up[i]
  if down[len(up)-1] - up[len(up)-k -1] - 1 > ans:
    ans = down[len(up)-1] - up[len(up)-k -1] - 1
print(ans)

Submission status: Accepted

Solution code:
n, k = [int(i) for i in input().split()]
s = input()

l = []
if s[0] == "0":
    l.append(0)
one = []
cnt_0 = 0
cnt_1 = 0

for i in s:
    if i == '0':
        if cnt_1 != 0:
            l.append(cnt_1)
            one.append((cnt_1))
            cnt_1 = 0
        cnt_0 += 1
    if i =='1':
        if cnt_0 != 0:
            l.append(cnt_0)
            cnt_0 = 0
        cnt_1 += 1

if cnt_1 != 0:
    l.append(cnt_1)
    one.append(cnt_1)
if cnt_0 != 0:
    l.append(cnt_0)
    l.append(0)

#print(l)
ans = 0
Sum = [0]
for i in range(len(l)):
    Sum.append(l[i]+Sum[i])
#print(Sum)

for i in range(1,len(Sum),2):
    left = i-1
    if i+k*2 > len(Sum)-1:
        right = len(Sum)-1
    else:
        right = i+k*2
    #print(left,right)
    temp = Sum[right] - Sum[left]
    if ans < temp:
        ans = temp
print(ans)

Submission status: Accepted

Solution code:
n, k = [int(i) for i in input().split()]
s = [int(i) for i in input()]

p = []
counter = 1
if s[0] == 0:
    p.append(0)
for i in range(1, n):
    if s[i] == s[i-1]:
        counter += 1
    else:
        p.append(counter)
        counter = 1
p.append(counter)

l = p[0::2] + [0, 0]
r = p[1::2]

counter = sum(r[:k]) + sum(l[:k+1])
imax = counter
for i in range(k, len(r)):
    counter += l[i+1] + r[i]
    counter -= l[i-k] + r[i-k]
    if counter > imax:
        imax = counter

print(imax)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S = list(map(int,input()))
tmp = 1
nums = []
cont = 0
for s in S:
    if int(s) == tmp:
        cont += 1
    else:
        nums.append(cont)
        cont = 1
        tmp = 1 - tmp
if cont != 0:
    nums.append(cont)
if len(nums) % 2 == 0:
    nums.append(0)
cml = [0]
for n in nums:
    cml.append(cml[-1]+n)
ans = []
for i in range(0,len(cml),2):
    ans.append(cml[min(len(cml)-1,i+K*2+1)]-cml[i])
print(max(ans))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = list(input())

seq = []
tmp = 0
for i in range(N-1):
    if S[i] != S[i+1]:
        tmp += 1
        seq.append(tmp)
        tmp = 0
            
    else:
        tmp += 1

seq.append(tmp+1)

seq_sum = [0 for _ in range(len(seq)+1)]

for i in range(len(seq)):
    seq_sum[i+1] = seq_sum[i] + seq[i]

res = -1
if S[0] == '0':
    for i in range(len(seq_sum)):
        if i%2 == 0:
            r = min(i + 2*K, len(seq_sum)-1)
            res = max(res, seq_sum[r] - seq_sum[i]) 
        else:
            r = min(i + 2*K+1, len(seq_sum)-1)
            res = max(res, seq_sum[r] - seq_sum[i])
        
else:
    for i in range(len(seq_sum)):
        if i%2 == 0:
            r = min(i + 2*K+1, len(seq_sum)-1)
            res = max(res, seq_sum[r] - seq_sum[i])
        else:
            r = min(i + 2*K, len(seq_sum)-1)
            res = max(res, seq_sum[r] - seq_sum[i]) 

            
print(res)

Submission status: Accepted

Solution code:
N,K = list(map(int,input().split()))
S = [int(i) for i in list(input())]
S.append(2)

S2 = []
cnt = 1
for i in range(N):
    if S[i] != S[i+1]:
        S2.append([S[i],cnt])
        cnt = 1
    else:
        cnt += 1

if S2[0][0] == 0:
    S2 = [[1,0]] + S2
if S2[-1][0] == 0:
    S2.append([1,0])    
    
SUM = [0]
for i in range(len(S2)):
    SUM.append(SUM[i] + S2[i][1])
T = []
for i in range(0,max(1,len(SUM)//2-K),1):
    T.append(SUM[min(len(SUM)-1,2*(K+i)+1)]-SUM[2*i])
print(max(T))

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
s = input()

if s[0]=='1':
    l = [1]
else:
    l = [0,1]

for i in range(1,n):
    if s[i] ==s[i-1]:
        l[-1]+=1
    else:
        l.append(1)

prev = sum(l[0:2*k+1])
ans = prev
for i in range(len(l)//2+1):
    prev = prev-sum(l[2*i:2*i+2]) + sum(l[2*i+2*k+1:2*i+2*k+3])
    ans = max(ans, prev)

print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = list(input())
a = []
switch = 0
tmp = 0
for i in range(n):
    if switch == 0:
        if s[i] == "1":
            tmp += 1
        else:
            a.append(tmp)
            tmp = 1
            switch = 1
    else:
        if s[i] == "0":
            tmp += 1
        else:
            a.append(tmp)
            tmp = 1
            switch = 0
a.append(tmp)

tmp = 0
if k*2 <= len(a):
    tmp = k
else:
    if len(a)%2 == 0:
        tmp = int(len(a)/2)
    else:
        tmp = len(a)//2 


ans = sum(a[0:tmp*2+1])
tmpans = sum(a[0:tmp*2+1])
i = 2
while i+tmp*2<=len(a):
    tmpans -= a[i-2]+a[i-1]
    if i+tmp*2 == len(a):
        tmpans += a[i+tmp*2-1]
    else:
        tmpans += a[i+tmp*2-1]+a[i+tmp*2] 
    ans = max(ans,tmpans)
    i+=2
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
if set(list(s)) == 1:
    print(n)
    exit

s = '0' + s + '0'
list_ones = []
for i in range(1, n+1):
    if s[i-1] == '0' and s[i] == '1':
        i_start = i
    if s[i] == '1' and s[i+1] == '0':
        i_end = i
        list_ones.append((i_start, i_end))
list_ones = [(1, 1)] + list_ones + [(n, n)]
# print(list_ones)

ans = 0
for j, (i_start, _) in enumerate(list_ones):
    j_end = min(len(list_ones)-1, j+k)
    _, i_end = list_ones[j_end]
    ans = max(ans, i_end-i_start+1)
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
if(n == 1):
    print("1")
    exit()
s = input()
zero = []
one = []
sp = [-1]
for i in range(len(s)-1):
    if(s[i] != s[i+1]):
        sp.append(i)
sp.append(len(s)-1)
spp =[]
if(s[0] == "0"):spp.append(0)
for i in range(1,len(sp)):
    spp.append(sp[i]-sp[i-1])

if(s[-1] == "0"):spp.append(0)

if((len(spp)-1)//2 <= k): 
    print(n)
    exit()

sum = 0
for i in range(2*k+1):
    sum += spp[i]
ans = sum
for i in range(2*k,len(spp)-2,2):
    sum = sum+spp[i+1]+spp[i+2]-spp[i-2*k]-spp[i-2*k+1]
    ans = max(sum,ans)

print(ans)

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 124
# https://atcoder.jp/contests/abc124
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def grouping(N, S):
    group = []
    s = S[0]
    c = 1
    for i in range(1, N):
        if S[i] == s:
            c += 1
        else:
            group.append((s, c))
            s = S[i]
            c = 1
    group.append((s, c))
    return group

def main(N, K, S):
    g = grouping(N, S)
    glen = len(g)
    # 累積和(cumsum)
    cs = [0] * (glen + 1)
    for i in range(glen):
        cs[i+1] = cs[i] + g[i][1]
    nm = 0
    for i in range(glen):
        if g[i][0] == '0':
            n = cs[min(i + 2*K, glen)] - cs[i]
        else:
            n = cs[min(i + 2*K+1, glen)] - cs[i]
        if n > nm:
            nm = n
    print(nm)

N, K = i2nn()
S = i2s()
main(N, K, S)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator


# globals
inf = float('inf')
N, K = 0, 0
S = ""
M = 300000


def set_inputs():
    global N, K, S
    N, K = get_li()
    S = get_str()
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    cont = []
    cur = S[0]
    count = 1
    for s in S[1:]:
        if cur == s:
            count += 1
        else:
            cont.append(count)
            cur = s
            count = 1
    cont.append(count)
    
    lc = len(cont)
    if lc == 1:
        print(len(S))
        return
    cont = cont + ([0] * M)
    if S[0] == "0":
        cont = [0] + cont
    ans = 0
    tmp = sum(cont[:2*K+1])
    ans = tmp
    i = 2
    while i < lc + 1:
        tmp = tmp - cont[i-2] - cont[i-1] + cont[i+2*K-1] + cont[i+2*K]
        ans = max(ans, tmp)
        i += 2
    print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator


# globals
inf = float('inf')
N, K = 0, 0
S = ""
M = 300000


def set_inputs():
    global N, K, S
    N, K = get_li()
    S = get_str()
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    cont = []
    cur = S[0]
    count = 1
    for s in S[1:]:
        if cur == s:
            count += 1
        else:
            cont.append((count, cur == "1"))
            cur = s
            count = 1
    cont.append((count, cur == "1"))
    
    lc = len(cont)
    if lc == 1:
        print(len(S))
        return
    cont = cont + ([(0, None)] * M)
    if cont[0][1] == False:
        cont = [(0, None)] + cont
    ans = 0
    tmp = sum(map(operator.itemgetter(0), cont[:2*K+1]))
    ans = tmp
    i = 2
    while i < lc + 1:
        tmp = tmp - cont[i-2][0] - cont[i-1][0] + cont[i+2*K-1][0] + cont[i+2*K][0]
        ans = max(ans, tmp)
        i += 2
    print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
k = int(input().split(" ")[1])
s = input()

arr = []
if s[0] is "0": 
  arr.append(0)
arr.append(1)
for i in range(1,len(s)):
  if s[i-1] is s[i]:
    arr[-1] += 1
  else:
    arr.append(1)
if s[-1] is "0": 
  arr.append(0)

sums = [0]
for i in range(len(arr)):
  sums.append(sums[i] + arr[i])
t = 2*k+1
m = 0
for i in range(0,len(arr),2):
  m = max(m,sums[min(len(sums)-1,i+t)]-sums[i])
print(m)

Submission status: Accepted

Solution code:
l = input().split(" ")
n = int(l[0])
k = int(l[1])
s = input()

nums = []
now = 1
count = 0
# まずは1-0-1-0の各回数を取る
for i in range(n):
    if s[i] == str(now):
        count = count + 1
    else:
        nums.append(count)
        now = 1 - now
        count = 1

if count != 0:
    nums.append(count)

# ラストは1
if len(nums) % 2 == 0:
    nums.append(0)

add = 2 * k + 1

sums = list((0, ))
for i in range(len(nums)):
    sums.append(sums[i] + nums[i])

ans = 0
# 偶数だけ
for i in range(len(nums))[::2]:
    left = i
    right = min(i + add, len(nums))
    tmp = sums[right] - sums[left]

    ans = max(tmp, ans)
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
A = []
if S[0] == '0':
  A.append(0)
i = 0
while i < len(S):
  j = i
  while j < len(S) and S[i] == S[j]:
    j += 1
  A.append(j - i)
  i = j
ans = 0
tot = 0
r = 0
for l in range(len(A)):
  while r < len(A) and r - l < 2 * K + 1:
    tot += A[r]
    r += 1
  if l % 2 == 0:
    ans = max(ans, tot)
  if r == l:
    r += 1
  else:
    tot -= A[l]
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=list(map(int,input()))
sp_list=[]
sum=0
sum_0=0
for i in range(n):
  if s[i]==1:
    sum+=1
    if sum_0>0:
      sp_list.append(sum_0)
    sum_0=0
    if i==(n-1):
      sp_list.append(sum)
  else:
    if i==0:
      sp_list.append(0)
    if i>0 and sum>0:
      sp_list.append(sum)
    sum_0+=1
    sum=0
    if i==(n-1):
      sp_list.append(sum_0)
      sp_list.append(0)
sum_list=[0]
sum=0
for i in range(len(sp_list)):
  sum+=sp_list[i]
  sum_list.append(sum)
length=min(k,len(sum_list))
if 2*k+1>=len(sum_list):
  print(sum_list[-1])
else:
  temp=0
  for i in range((len(sum_list)-2*k)//2):
    if temp<(sum_list[2*i+2*k+1]-sum_list[2*i]):
      temp=(sum_list[2*i+2*k+1]-sum_list[i*2])
  print(temp)

Submission status: Accepted

Solution code:
import sys
def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N,K = map(int, input().split())
    S = sys.stdin.readline()
  else:
    # For Test
    # N = 5
    # K = 1
    # S = "00010"
    # N = 14
    # K = 2
    # S = "11101010110011"
    # N = 1
    # K = 1
    # S = "1"
    N = 5
    K = 1
    S = "11111"
    
  SC = []
  i = 0
  if S[0] == "0":SC.append(0)
  while i < N :
    if S[i] == "0":
      j = S.find("1",i)
    else:
      j = S.find("0",i)
    if j == -1: j = N 
    cnt = j - i
    i = j
    SC.append(cnt)
    
  if 'get_ipython' in globals(): print(SC)
    
  SH = []
  cnt = 0
  for i in range(len(SC)):
    cnt += SC[i]
    SH.append(cnt)
  
  if 'get_ipython' in globals(): print(SH)
  
  lenSC = len(SC) - 1
  ans = 0
  for i in range(0,lenSC+1,2):
    k = i + K * 2
    if k > lenSC:
      k = lenSC
    if i != 0:
      cnt = SH[k] - SH[i-1]
    elif k == i:
      cnt = SH[k]
    else:
      cnt = SH[k] - SH[i]
    if ans < cnt: ans = cnt

  print(ans)

main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()

A = []
if S[0] == '0':
  A.append(0)

i = 0
while i < len(S):
  j = i
  while j < len(S) and S[i] == S[j]:
    j += 1
  A.append(j - i)
  i = j

ans = 0
tot = 0
r = 0

for l in range(len(A)):
  while r < len(A) and r - l < 2 * K + 1:
    tot += A[r]
    r += 1
  if l % 2 == 0:
    ans = max(ans, tot)
  if l == r:
    r += 1
  else:
    tot -= A[l]

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
S += '2'

A = []
if S[0] == '0':
  A.append(0)

cnt = 1
for i in range(1, len(S)):
  if S[i] == S[i-1]:
    cnt += 1
  else:
    A.append(cnt)
    cnt = 1

ans = 0
tot = 0
r = 0

for l in range(len(A)):
  while r < len(A) and r - l < 2 * K + 1:
    tot += A[r]
    r += 1
  if l % 2 == 0:
    ans = max(ans, tot)
  if l == r:
    r += 1
  else:
    tot -= A[l]

print(ans)

Submission status: Accepted

Solution code:
n, k = map(int,input().split())
s = list(map(int,list((input()))))

l = [0]

for i in range(0,n-1):
    if s[i] != s[i+1]:
        l.append(i+1)

t = len(l)

for x in range(0,2*k+1):
    l.append(n)

#print(l)

can = []

for j in range(0,t):
    if s[l[j]] == 0:
        can.append(l[j+2*k]-l[j])
    elif s[l[j]] == 1:
        can.append(l[j+2*k+1]-l[j])
    else:
        break

#print(can)
print(max(can))

Submission status: Accepted

Solution code:
import numpy as np

N,K = map(int, input().split())
S = [int(x) for x in input()]

memo = np.zeros(10**5+1, dtype = np.int64)
W = min(2*K, 10**5)

current = 1 # 最初は1が0個ある
p = 0

for x in S:
  if x == current:
    memo[p] += 1
  else:
    current = 1 - current
    p += 1
    memo[p] += 1

ans = memo[:W+1].sum()
x = ans
for r in range(2,10**5+1,2):
  if r+W > 10**5:
    break
  x = x-memo[r-2]-memo[r-1]+memo[r+W]+memo[r+W-1]
  if x > ans:
    ans = x

print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
s=list(input())

S=[]
F="2"
cnt=0
for i in range(N):
    if F=="0":
        if s[i]=="0":
            cnt-=1
        else:
            S.append(cnt)
            F="1"
            cnt=1
    elif F=="1":
        if s[i]=="1":
            cnt+=1
        else:
            S.append(cnt)
            F="0"
            cnt=-1
    else:
        if s[i]=="0":
            F="0"
            cnt=-1
        else:
            F="1"
            cnt=1
S.append(cnt)
if S[0]<0:
    S=[0]+S+[0]
else:
    S=S+[0]

if S[0]>=0:
    if len(S)<=(2*K+1):
        ans=0
        for i in range(len(S)):
            ans+=abs(S[i])
        print(ans)
        #exit()
    else:
        ans=0
        SUM=0
        for i in range(2*K+1):
            SUM+=abs(S[i])
            ans=SUM
        #print(ans)
        for i in range(1,len(S)):
            if (2*i+2*K)>(len(S)-1):
                #print("A")
                break
            else:
                #print("B")
                SUM=SUM+abs(S[2*i+2*K-1])+abs(S[2*i+2*K])-abs(S[2*i-1])-abs(S[2*i-2])
                if SUM>ans:
                    ans=SUM
        print(ans)
        #exit()
#print(S)

Submission status: Accepted

Solution code:
import numpy as np

N, K = map(int, input().split())
S = input()

nums = np.array([len(s) for s in S.replace('10', '1,0').replace('01', '0,1').split(',')])

if S[0] == '0':
    nums = np.insert(nums, 0, 0)

if len(nums) % 2 == 0:
    nums = np.insert(nums, len(nums), 0)

csm = np.insert(nums.cumsum(), 0, 0)

res = 0
for i in range(0, len(nums), 2):
    left = i
    right = min(2*K+1 + i, len(nums))
    res = max(res, csm[right] - csm[left])
print(res)

Submission status: Accepted

Solution code:
lftIdx, rgtIdx, ans = 0, 0, 0
lftFlg, rgtFlg = False, False
n, k = map(int, input().split())
s = input()


def move(lr, idx, flg):
    # lr: lft := "1", rgt := "0"
    # return: idx
    global s
    if flg and idx < n-1:
        idx += 1
    contains_zero = False
    while True:
        if idx == n-1:
            return idx
        if s[idx] == "0":
            contains_zero = True
        if contains_zero and s[idx] != s[idx+1] and s[idx+1] == lr:
            return idx
        idx += 1


def solv():
    global lftIdx, rgtIdx, ans, lftFlg, rgtFlg, n, k, s
    for i in range(k):
        rgtIdx = move("0", rgtIdx, rgtFlg)
        rgtFlg = True
    ans = max(ans, rgtIdx + 1)
    while n-1 > rgtIdx:
        rgtIdx = move("0", rgtIdx, rgtFlg)
        lftIdx = move("1", lftIdx, lftFlg)
        lftFlg = True
        ans = max(ans, rgtIdx - lftIdx)  # (rgtIdx + 1) - (lftIdx + 1)
    return


solv()
print(ans)