Problem: 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.

Submission attempts (in order):
import sys
stdin = sys.stdin 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

def Solve():
    N,K=na();S=ns()
    l=[]
    N=len(S)
    if(S[0]=="0"):
        l.append(0)
    b=S[0]
    ct=1
    for i in S[1:]:
        if(b!=i):
            l.append(ct)
            ct=1
            b=i
        else:
            ct+=1
    l.append(ct)
    len_l=len(l)
    if(len_l//2 <= K):
        return sum(l)
    ans = res = sum(l[:2*K+1])
    
    if(len_l%2==0):
        l.append(0)
        len_l+=1
    g = K * 2 + 1
    for i in range(K*2+1,len_l-1,2):
        ans -= l[i-g] + l[i-g+1]
        ans += l[i] + l[1+i]
        if(res<ans):
            res=ans
    print(S)
    print(l)
    print(len_l)
    return res

print(Solve())

import sys
stdin = sys.stdin 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()
N,K=na();S=na()
l=[]
N=len(S)
if(S[0]==0):
    l.append(0)
b=S[0]
ct=1
for i in S[1:]:
    if(b!=i):
        l.append(ct)
        ct=1
        b=i
    else:
        ct+=1
l.append(ct)

len_l=len(l)
if(len_l//2 <= K):
    print(sum(l))
    exit()

if(len_l%2==0):
    l.append(0)
    len_l+=1
res = sum(l[:2*K+1])
ans=res
for i in range(K*2+1,len_l-1,2):
    ans -= l[i-(2*K+1)] + l[i+1-(2*K+1)]
    ans += l[i] + l[1+i]
    res = max(ans,res)
#print(l)
print(res)

import sys
stdin = sys.stdin 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()
N,K=na();S=ns()
l=[]
c1=0
c0=0
x0=0
first=True
if(S[0]=="1"):
    c1=1
else:
    c0=1
for i in range(1,N):
    if(S[i]=="1"):
        if(S[i]!=S[i-1]):
            l.append(c0)
            c0=0
        c1+=1
    else:
        if(S[i]!=S[i-1]):
            x0+=1
            l.append(c1)
            c1=0
        c0+=1
if(c1):
    l.append(c1)
else:
    x0+=1
    l.append(c0)
#print(l)
#print(x0)
if(x0<=K):
    print(N)
    exit()
else:
    res=0
    if(int(S[0])>0):
        if(int(S[-1])>0):
            right = 0
            left = 2*K
            while(True):
                if(left>=len(l)):
                    print(res)
                    exit()
                res=max(sum(l[right:left+1]),res)
                #print(res,right,left)
                right+=2
                left+=2
        else:
            right = 0
            left = 2*K
            #print("llll")
            res=max(sum(l[len(l)-(1+(K-1)*2)-1:]),res)
            
            while(True):
                if(left>=len(l)-1):
                    print(res)
                    exit()
                res=max(sum(l[right:left+1]),res)
                #print(res,right,left)
                right+=2
                left+=2
    else:
        if(int(S[-1])>0):
            res=max(res,sum(l[0:2*K]))
            right = 1
            left = 2*K+1
            while(True):
                if(left>=len(l)):
                    print(res)
                    exit()
                res=max(sum(l[right:left+1]),res)
                #print(res,right,left)
                right+=2
                left+=2
        else:
            right = 0
            left = 2*K
            
            res=max(sum(l[len(l)-(1+(K-1)*2)-1:]),res)
            
            res=max(res,sum(l[0:2*K]))
            right = 1
            left = 2*K+1
            while(True):
                if(left>=len(l)-1):
                    print(res)
                    exit()
                res=max(sum(l[right:left+1]),res)
                #print(res,right,left)
                right+=2
                left+=2


import sys
stdin = sys.stdin 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()
N,K=na();S=ns()
l=[]
c1=0
c0=0
x0=0
first=True
if(S[0]=="1"):
    c1=1
else:
    c0=1
for i in range(1,N):
    if(S[i]=="1"):
        if(S[i]!=S[i-1]):
            l.append(c0)
            c0=0
        c1+=1
    else:
        if(S[i]!=S[i-1]):
            x0+=1
            l.append(c1)
            c1=0
        c0+=1
if(c1):
    l.append(c1)
else:
    x0+=1
    l.append(c0)
#print(l)
#print(x0)
if(x0<=K):
    print(N)
    exit()
else:
    res=0
    if(int(S[0])>0):
        if(int(S[-1])>0):
            right = 0
            left = 2*K
            while(True):
                if(left>=len(l)-1):
                    print(res)
                    exit()
                res=max(sum(l[right:left+1]),res)
                #print(res,right,left)
                right+=2
                left+=2
        else:
            right = 0
            left = 2*K
            #print("llll")
            res=max(sum(l[len(l)-(1+(K-1)*2)-1:]),res)
            
            while(True):
                if(left>=len(l)-3):
                    print(res)
                    exit()
                res=max(sum(l[right:left+1]),res)
                #print(res,right,left)
                right+=2
                left+=2
    else:
        if(int(S[-1])>0):
            res=max(res,sum(l[0:2*K]))
            right = 1
            left = 2*K+1
            while(True):
                if(left>=len(l)-1):
                    print(res)
                    exit()
                res=max(sum(l[right:left+1]),res)
                #print(res,right,left)
                right+=2
                left+=2
        else:
            right = 0
            left = 2*K
            
            res=max(sum(l[len(l)-(1+(K-1)*2)-1:]),res)
            
            res=max(res,sum(l[0:2*K]))
            right = 1
            left = 2*K+1
            while(True):
                if(left>=len(l)-3):
                    print(res)
                    exit()
                res=max(sum(l[right:left+1]),res)
                #print(res,right,left)
                right+=2
                left+=2


import sys
stdin = sys.stdin 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()
N,K=na();S=na()
l=[]
N=len(S)
if(S[0]=="0"):
    l.append(0)
b=S[0]
ct=1
for i in S[1:]:
    if(b!=i):
        l.append(ct)
        ct=1
        b=i
    else:
        ct+=1
l.append(ct)

len_l=len(l)
if(len_l//2 <= K):
    print(sum(l))
    exit()

if(len_l%2==0):
    l.append(0)
    len_l+=1
res = sum(l[:2*K+1])
ans=res
for i in range(K*2+1,len_l-1,2):
    ans -= l[i-(2*K+1)] + l[i+1-(2*K+1)]
    ans += l[i] + l[1+i]
    res = max(ans,res)
#print(l)
print(res)

import sys
stdin = sys.stdin 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()
N,K=na();S=ns()
l=[]
c1=0
c0=0
x0=0
first=True
if(S[0]=="1"):
    c1=1
else:
    c0=1
for i in range(1,N):
    if(S[i]=="1"):
        if(S[i]!=S[i-1]):
            l.append(c0)
            c0=0
        c1+=1
    else:
        if(S[i]!=S[i-1]):
            x0+=1
            l.append(c1)
            c1=0
        c0+=1
if(c1):
    l.append(c1)
else:
    x0+=1
    l.append(c0)
#print(l)
#print(x0)
if(x0<=K):
    print(N)
    exit()
else:
    res=0
    if(int(S[0])>0):
        if(int(S[-1])>0):
            right = 0
            left = 2*K
            while(True):
                if(left>=len(l)-1):
                    print(res)
                    exit()
                res=max(sum(l[right:left+1]),res)
                #print(res,right,left)
                right+=2
                left+=2
        else:
            right = 0
            left = 2*K
            #print("llll")
            res=max(sum(l[len(l)-(1+(K-1)*2)-1:]),res)
            
            while(True):
                if(left>=len(l)-1):
                    print(res)
                    exit()
                res=max(sum(l[right:left+1]),res)
                #print(res,right,left)
                right+=2
                left+=2
    else:
        if(int(S[-1])>0):
            res=max(res,sum(l[0:2*K]))
            right = 1
            left = 2*K+1
            while(True):
                if(left>=len(l)-1):
                    print(res)
                    exit()
                res=max(sum(l[right:left+1]),res)
                #print(res,right,left)
                right+=2
                left+=2
        else:
            right = 0
            left = 2*K
            
            res=max(sum(l[len(l)-(1+(K-1)*2)-1:]),res)
            
            res=max(res,sum(l[0:2*K]))
            right = 1
            left = 2*K+1
            while(True):
                if(left>=len(l)-1):
                    print(res)
                    exit()
                res=max(sum(l[right:left+1]),res)
                #print(res,right,left)
                right+=2
                left+=2


import sys
stdin = sys.stdin 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

def Solve():
    N,K=na()
    S=input()
    l=[]
    N=len(S)
    #print(len(S))
    if(S[0]=="0"):
        #print("00")
        l.append(0)
    t=S[0]
    ct=1
    #print("aa")
    #print(S)
    #print(S[0],S[1],S[2])
    for b in S[1:]:
        #print(b)
        if(t!=b):
            l.append(ct)
            ct=1
            t=b
        else:
            ct+=1
    #print("bb")
    l.append(ct)
    len_l=len(l)
    if(len_l//2 <= K):
        return sum(l)
    ans = res = sum(l[:2*K+1])
    
    if(len_l%2==0):
        l.append(0)
        len_l+=1
    g = K * 2 + 1
    for i in range(K*2+1,len_l-1,2):
        ans -= l[i-g] + l[i-g+1]
        ans += l[i] + l[1+i]
        if(res<ans):
            res=ans
    #print(S)
    #print(l)
    #print(len_l)
    return res

print(Solve())

Verdicts: Wrong Answer

Wrong Answer

Runtime Error

Runtime Error

Wrong Answer

Runtime Error

Accepted