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: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=1000000007
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# Summarize count of factor within list -- START --
def summarize_list(sl):

  a=sl[0]
  c=1
  res=[]

  for x in sl[1:]:
    if x==a:
      c+=1
    else:
      res.append(c)
      a=x
      c=1
  res.append(c)

  return res
# Summarize count of factor within list --- END ---

def main():
  n,k=LI()
  s=list(S())

  l=summarize_list(s)
  # print(l)

  # 累積和
  for i in range(len(l)-1):
    l[i+1]+=l[i]

  # 1 0 1 0... の形にする
  if s[0]=='0':
    l=[0]+l

  # ...0 1 0 1 の形にする
  if len(l)%2==0:
    l+=[0]

  # 尺取のスタート
  l=[0]+l
  # print(l)

  ans=0
  i1=0
  i2=min(len(l)-1,2*k+1)
  while True:
    if i2>=len(l):
      return ans

    ans=max(ans,l[i2]-l[i1])

    i1+=2
    i2+=2

# main()
print(main())

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=1000000007
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# Summarize count of factor within list -- START --
def summarize_list(sl):

  a=sl[0]
  c=1
  res=[]

  for x in sl[1:]:
    if x==a:
      c+=1
    else:
      res.append(c)
      a=x
      c=1
  res.append(c)

  return res
# Summarize count of factor within list --- END ---


def main():
  n,k=LI()
  s=list(S())

  l=summarize_list(s)
  # print(l)

  # 累積和
  for i in range(len(l)-1):
    l[i+1]+=l[i]

  ans=0
  if s[0]=='0':
    if (len(l)+1)//2<=k:
      return len(s)

    l=[0]+l
    i1=0
    i2=k*2
    while True:
      if i2>=len(l):
        return ans
      ans=max(ans,l[i2]-l[i1])
      if i2%2==0:
        i1+=2
        i2+=2
      else:
        i1+=1
        i2+=1

  else:

    if len(l)//2<=k:
      return len(s)

    l=[0]+l
    i1=0
    i2=k*2+1
    while True:
      if i2>=len(l):
        return ans
      ans=max(ans,l[i2]-l[i1])
      if i2%2==0:
        i1+=1
        i2+=1
      else:
        i1+=2
        i2+=2

# main()
print(main())

Submission status: Wrong Answer

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

prev = S[0]
renzoku_start = [0]
for i in range(1, N):
  if prev == S[i]:
    continue
  else:
    prev = S[i]
    renzoku_start.append(i)
renzoku_start.append(N)

ans = []
l = len(renzoku_start)
for j in range(l):
  if S[renzoku_start[j]] == 0:
    if j + 2 * K >= l:
      break
    ans.append(renzoku_start[j + 2 * K] - renzoku_start[j])
  else:
    if j + 2 * K + 1 >= l:
      break
    ans.append(renzoku_start[j + 2 * K + 1] - renzoku_start[j])

if ans:
  print(max(ans))
else:
  print(N)

Submission status: Wrong Answer

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

count = 1
Nums_count = []
now = s[0]
start = 0
for i in range(1,n):
    if s[i] == str(now):
        count += 1
    else:
        Nums_count.append([start, count])
        now = s[i]
        start = i
        count = 1
    if i == n-1:
        Nums_count.append([start, count])
if len(s) == 1:
    Nums_count.append([0,1])

Nums_count_rui = [[-1, 0]]
for i in range(len(Nums_count)):
    Nums_count_rui.append([Nums_count[i][0],Nums_count[i][1]+Nums_count_rui[-1][1]])

# print(Nums_count_rui)
ans = 0
m = len(Nums_count_rui)

if s[0] == '0' and m <= 2*k:
    ans = n
elif s[0] == '1' and m <= 2*k+1:
    ans = n

for i in range(1,m-2*k):
    if s[Nums_count_rui[i][0]] == '0':
        if i+2*k-1 >= m:
            tot = Nums_count_rui[-1][1] - Nums_count_rui[i-1][1]
        else:
            tot = Nums_count_rui[i+2*k-1][1] - Nums_count_rui[i-1][1]
    else:
        if i+2*k >= m:
            tot = Nums_count_rui[-1][1] - Nums_count_rui[i-1][1]
        else:
            tot = Nums_count_rui[i+2*k][1] - Nums_count_rui[i-1][1]
    ans = max(tot, ans)
print(ans)

Submission status: Wrong Answer

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

count = 1
Nums_count = []
now = s[0]
for i in range(1,n):
    if s[i] == str(now):
        count += 1
    else:
        now = s[i]
        Nums_count.append(count)
        count = 1
    if i == n-1:
        Nums_count.append(count)
if len(s) == 1:
    Nums_count.append(1)

Nums_count_rui = [0]
for i in range(len(Nums_count)):
    Nums_count_rui.append(Nums_count[i]+Nums_count_rui[-1])

ans = 0
m = len(Nums_count_rui)

if s[0] == '0' and m <= 2*k:
    ans = n
elif s[0] == '1' and m <= 2*k+1:
    ans = n

moji_count = 0
for i in range(m-2*k-1):
    moji_count = Nums_count_rui[i]
    if s[moji_count] == '0':
        if i+2*k >= m:
            tot = Nums_count_rui[-1] - Nums_count_rui[i]
        else:
            tot = Nums_count_rui[i+2*k] - Nums_count_rui[i]
    elif s[moji_count] == '1':
        if i+2*k+1 >= m:
            tot = Nums_count_rui[-1] - Nums_count_rui[i]
        else:
            tot = Nums_count_rui[i+2*k+1] - Nums_count_rui[i]
    ans = max(tot, ans)
print(ans)

Submission status: Wrong Answer

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

count = 1
Nums_count = []
now = s[0]
for i in range(1,n):
    if s[i] == str(now):
        count += 1
    else:
        now = s[i]
        Nums_count.append(count)
        count = 1
    if i == n-1:
        Nums_count.append(count)
if len(s) == 1:
    Nums_count.append(1)

Nums_count_rui = [0]
for i in range(len(Nums_count)):
    Nums_count_rui.append(Nums_count[i]+Nums_count_rui[-1])

ans = 0
m = len(Nums_count_rui)

if s[0] == '0':
    if k*2 >= m-1:
        ans = n
    else:
        for i in range(m-2*k):
            tot = Nums_count_rui[i+2*k] - Nums_count_rui[i]
            ans = max(tot, ans)
elif s[0] == '1':
    if k*2+1 >= m-1:
        ans = n
    else:
        for i in range(m-2*k-1):
            tot = Nums_count_rui[i+2*k+1] - Nums_count_rui[i]
            ans = max(tot, ans)
print(ans)

Submission status: Wrong Answer

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

count = 1
Nums_count = []
now = s[0]
for i in range(1,n):
    if s[i] == str(now):
        count += 1
    else:
        now = s[i]
        Nums_count.append(count)
        count = 1
    if i == n-1:
        Nums_count.append(count)
if len(s) == 1:
    Nums_count.append(1)

Nums_count_rui = [0]
for i in range(len(Nums_count)):
    Nums_count_rui.append(Nums_count[i]+Nums_count_rui[-1])

ans = 0
m = len(Nums_count_rui)

if s[0] == '0':
    if k*2 >= m:
        ans = n
    else:
        for i in range(0, m-2*k, 2):
            tot = Nums_count_rui[i+2*k] - Nums_count_rui[i]
            ans = max(tot, ans)
elif s[0] == '1':
    if k*2+1 >= m:
        ans = n
    else:
        for i in range(0, m-2*k-1, 2):
            tot = Nums_count_rui[i+2*k+1] - Nums_count_rui[i]
            ans = max(tot, ans)
print(ans)

Submission status: Wrong Answer

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

count = 1
Nums_count = []
now = s[0]
for i in range(1,n):
    if s[i] == str(now):
        count += 1
    else:
        now = s[i]
        Nums_count.append(count)
        count = 1
    if i == n-1:
        Nums_count.append(count)
if len(s) == 1:
    Nums_count.append(1)

Nums_count_rui = [0]
for i in range(len(Nums_count)):
    Nums_count_rui.append(Nums_count[i]+Nums_count_rui[-1])

ans = 0
m = len(Nums_count_rui)

if s[0] == '0':
    if k*2 >= m:
        ans = n
    else:
        for i in range(m-2*k):
            tot = Nums_count_rui[i+2*k] - Nums_count_rui[i]
            ans = max(tot, ans)
elif s[0] == '1':
    if k*2+1 >= m:
        ans = n
    else:
        for i in range(m-2*k-1):
            tot = Nums_count_rui[i+2*k+1] - Nums_count_rui[i]
            ans = max(tot, ans)
print(ans)

Submission status: Wrong Answer

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

change = [0]
for i, (e1, e2) in enumerate(zip(s, s[1:])):
	e1 = int(e1)
	e2 = int(e2)
	if e1 ^ e2:
		change.append(i + 1)

ln = len(change)
ans = 0
for l in change:
	if s[l] == "1":
		ri = l + 2 * k + 1
	else:
		ri = l + 2 * k

	ri = min(ri, ln - 1)
	r = change[ri]
	ans = max(ans, r - l)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

from itertools import groupby

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

S_groupby = groupby(S)

zero_idx = [] # ゼロが何番目か
value_list = [] # 各インデックスのキーに対する個数
i = -1
for j in S_groupby:
    i += 1
    key, value = j[0], len(list(j[1]))
    value_list.append(value)
    if key == '0':
        zero_idx.append(i)

if len(zero_idx) <= K:
    print(len(S))
    sys.exit()

left = zero_idx[0]
right = zero_idx[K - 1]
if zero_idx[0] == 0:
    ans = [sum(value_list[left:right + 2])]
else:
    ans = [sum(value_list[left - 1:right + 2])]

for i in range(K, len(zero_idx)):
    right = zero_idx[i]
    left = zero_idx[K - 1 - i]
    ans.append(sum(value_list[left - 1:right + 2]))

print(max(ans))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
s = input()
seq = []
pre = '1'
count = 0
for c in s:
    if c == pre:
        count += 1
    else:
        pre = c
        seq.append(count)
        count = 1
seq.append(count)

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

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
s = input()
seq = []
pre = '1'
count = 0
for c in s:
    if c == pre:
        count += 1
    else:
        pre = c
        seq.append(count)
        count = 1
seq.append(count)

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

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
s = input()
seq = []
pre = '1'
count = 0
for c in s:
    if c == pre:
        count += 1
    else:
        pre = c
        seq.append(count)
        count = 1
seq.append(count)

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

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
s = input()
seq = []
pre = '1'
count = 0
for c in s:
    if c == pre:
        count += 1
    else:
        pre = c
        seq.append(count)
        count = 1
seq.append(count)

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

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
s = input()
seq = []
pre = '1'
count = 0
for c in s:
    if c == pre:
        count += 1
    else:
        pre = c
        seq.append(count)
        count = 1
seq.append(count)

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

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
s = input()
seq = []
pre = '1'
count = 0
for c in s:
    if c == pre:
        count += 1
    else:
        pre = c
        seq.append(count)
        count = 1
seq.append(count)

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

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
s = input()
seq = []
pre = '1'
count = 0
for c in s:
    if c == pre:
        count += 1
    else:
        pre = c
        seq.append(count)
        count = 1
seq.append(count)

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

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
s = input()
seq = []
pre = '1'
count = 0
for c in s:
    if c == pre:
        count += 1
    else:
        pre = c
        seq.append(count)
        count = 1
seq.append(count)

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

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
s = input()
seq = []
pre = '1'
count = 0
for c in s:
    if c == pre:
        count += 1
    else:
        pre = c
        seq.append(count)
        count = 1
seq.append(count)

ans = 0
for i in range(n):
    ans = max(ans, sum(seq[i: 2 * k + 1 + i]))
print(ans)

Submission status: Wrong Answer

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

if s[0]=='0':
    seq=[0]
else:
    seq=[]

before=s[0]
cnt=0

for x in s:
    if x==before:
        cnt+=1
    else:
        before=x
        seq.append(cnt)
        cnt=1
if cnt>0:
    seq.append(cnt)

bleft=0
bright=min(2*k,len(seq)-1)

cursum=sum(seq[bleft:bright+1])
ret=cursum

for i in range(2,len(seq),2):
    left=i
    right=min(i+2*k,len(seq)-1)

    if bleft!=left:
        cursum-=seq[bleft]+seq[bleft+1]
        bleft=left
    if bright!=right:
        cursum+=seq[right-1]+seq[right]
        bright=right
    
    ret=max(ret,cursum)
    
print(ret)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
S=input()
C=[]
flag=False
count=0
prv=S[0]
if S[0]!="1":
    C.append(0)
"""
for i in range(N):
    if prv!=S[i]:
        C.append(count)
        count=1
    else:
        count+=1
    prv=S[i]
if count>0:
    C.append(count)
"""
tmp=0
for i in range(len(S)):
    if i<tmp:
        continue
    j=tmp
    while(S[j]==S[i]):
        j+=1
        if j==len(S):
            break
    C.append(j-i)
    tmp=j
if S[-1]=="0":
    C.append(0)
if len(C)==1:
    print(sum(C))
    exit()
ans=0
#print(C)
sums=[0]*(len(C)+1)
sums.append(0)
for i in range(len(C)):
    sums[i+1]=sums[i]+C[i]
#print(sums)
for left in range(0,len(sums),2):
    right=left+2*K+1
    if right>=len(sums):
        right=int(len(sums))-1
    ans=max(ans,sums[right]-sums[left])
print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
S=input()
C=[]
flag=False
count=0
prv=S[0]
if S[0]!="1":
    C.append(0)
"""
for i in range(N):
    if prv!=S[i]:
        C.append(count)
        count=1
    else:
        count+=1
    prv=S[i]
if count>0:
    C.append(count)
"""
tmp=0
for i in range(len(S)):
    if i<tmp:
        continue
    j=tmp
    while(S[j]==S[i]):
        j+=1
        if j==len(S):
            break
    C.append(j-i)
    tmp=j
if S[-1]=="0":
    C.append(0)

ans=0
#print(C)
sums=[0]*(len(C)+1)
sums.append(0)
for i in range(len(C)):
    sums[i+1]=sums[i]+C[i]
#print(sums)
for left in range(0,len(sums),2):
    right=left+2*K+1
    if right>=len(sums):
        right=int(len(sums))-1
    ans=max(ans,sums[right]-sums[left])
print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
S=input()
C=[]
flag=False
count=0
prv=S[0]
if S[0]!="1":
    C.append(0)
"""
for i in range(N):
    if prv!=S[i]:
        C.append(count)
        count=1
    else:
        count+=1
    prv=S[i]
if count>0:
    C.append(count)
"""
tmp=0
for i in range(len(S)):
    if i<tmp:
        continue
    j=tmp
    while(S[j]==S[i]):
        j+=1
        if j==len(S):
            break
    C.append(j-i)
    tmp=j
if S[-1]=="0":
    C.append(0)

ans=0
print(C)
sums=[0]*(len(C)+1)
sums.append(0)
for i in range(len(C)):
    sums[i+1]=sums[i]+C[i]
#print(sums)
for left in range(0,len(sums),2):
    right=left+2*K+1
    if right>=len(sums):
        right=int(len(sums))-1
    ans=max(ans,sums[right]-sums[left])
print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
S=input()
C=[]
flag=False
count=0
prv=S[0]
if S[0]!="1":
    C.append(0)
for i in range(N):
    if prv!=S[i]:
        C.append(count)
        count=1
    else:
        count+=1
    prv=S[i]
if count>0:
    C.append(count)
if S[-1]=="0":
    C.append(0)

ans=0
#print(C)
sums=[0]*(len(C)+1)
sums.append(0)
for i in range(len(C)):
    sums[i+1]=sums[i]+C[i]
#print(sums)
for left in range(0,len(sums),2):
    right=left+2*K+1
    if right>=len(sums):
        right=int(len(sums))-1
    ans=max(ans,sums[right]-sums[left])
print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
S=input()
C=[]
flag=False
count=0
prv=S[0]
if S[0]!="1":
    C.append(0)
for i in range(N):
    if prv!=S[i]:
        C.append(count)
        count=1
    else:
        count+=1
    prv=S[i]
if count>0:
    C.append(count)
if S[-1]=="0":
    C.append(1)

ans=0
#print(C)
sums=[0]*len(C)
sums.append(0)
for i in range(len(C)):
    sums[i+1]=sums[i]+C[i]
#print(sums)
for left in range(0,len(sums),2):
    right=left+2*K+1
    if right>=len(sums):
        right=int(len(sums))-1
    ans=max(ans,sums[right]-sums[left])
print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
S=input()
C=[]
flag=False
count=0
prv=S[0]
if S[0]!="1":
    C.append(0)
for i in range(N):
    if prv!=S[i]:
        C.append(count)
        count=1
    else:
        count+=1
    prv=S[i]
if count>0:
    C.append(count)
ans=0
#print(C)
if len(C)==1:
    print(sum(C))
    exit()
for i in range(len(C)):
    tmp=0
    if i%2!=0:
        continue
    if(i+2*K)>=len(C):
        break
    for j in range(i,i+2*K+1):
        tmp+=C[j]
        #print(j)
    #print("ON")
    ans=max(ans,tmp)
print(ans)

Submission status: Wrong Answer

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

L = [0]
tmp = '1'

"""
下記をLに格納する。

0,2,4,6...番目のidxは1の値の個数
1,3,5,7,...番目のidxは0の値の個数

また、Lの最後の要素は「1の値の個数」となるようにする。
（なので、0になることもある）
これで、無理やりLの要素数を必ず奇数になるように強制する。
これで「1の値の個数」で始まって終わる配列を取得する。
"""

for s in S:
  if s == tmp:
    L[-1] += 1
  else:
    L.append(1)
  tmp = s

if tmp == '0':
  L.append(0)


## 全てを1、もしくは0で表現できてしまう場合は文字列の長さをそのまま出力する
M = len(L)
if M <= 2*K+1:
  ans = N
  exit()


## 累積を計算
## 最初の要素は使わない（下記のループを簡単に書くために要素を一個多くしているだけ）
X = [0]*(M+1)
for i in range(M):
  X[i+1] = X[i] + L[i]


## answer
ans = 0
for m in range(0,M-2*K,2):
  _ = X[2*K+m+1]-X[m]
  ans = max(ans, _)


print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
S=input()
L=[0]
#even:1
#odd:0
tmp="0"
for i in range(N):
    if tmp!=S[i]:
        L.append(1)
    else:
        L[-1]+=1
    tmp=S[i]

if tmp=="0":
    L.append(0)


M=len(L)
## 1しか無い場合は長さを出力して終わり
if M<=2*K+1:
    print(N)
    exit()


X=[0 for i in range(M+1)]
for i in range(M):
    X[i+1]=L[i]+X[i]


ans=0
for i in range(0,M-2*K,2):
    #print(X[i],X[i+2*K+1])
    ans=max(ans,X[i+2*K+1]-X[i])
print(ans)

Submission status: Wrong Answer

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

"""考え方
0で区切られているところをくっつけた時のながさ、を尺取り方式で計算する
"""

## 1.0,1のidxを特定
## 連続する0,1の「最初の位置」を格納する。
list_idx_0_start = []
list_idx_0_end = []
pre_s = ''
for s in range(N):
  _ = S[s]
  if _ != pre_s:
    if _ == '0':
      list_idx_0_start.append(s)
    elif _ == '1':
      list_idx_0_end.append(s)
    else:
      pass
  pre_s = S[s]

## 2.計算
## 一番大きい値が答え
max_loop_cnt = len(list_idx_0_start)
ans = 0
## 2-1.0が前
if S[0] == '0':
  for k in range(max_loop_cnt-K):
    _ = list_idx_0_start[k+K] - list_idx_0_start[k]
    ans = max(ans,_)
## 2-2.0が後
elif S[0] == '1':
  ## それ以降はループ
  for k in range(0,max_loop_cnt-K):
    _ = list_idx_0_start[k+K] - list_idx_0_end[k]
    ans = max(ans,_)  

## 3.例外処理
## 0が一個も無い
if max_loop_cnt == 0:
  ans = N

print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from itertools import groupby,accumulate
n,k = map(int,stdin.readline().rstrip().split())
s = stdin.readline().rstrip()
li = []
for key, value in groupby(s):
    li.append((key,len(list(value))))
#とりあえず逆立ちしている人（透明人間含）でサンドイッチしていることにする
if li[0][0] != "1":
    li = [("1",0)]+li
if li[-1][0] != "1":
    li.append(("1",0))
lin = [i[1] for i in li]
lin = [0,0]+list(accumulate(lin))
ma = lin[2]#とりうる最大の人数
for i in range((k+1)*2,len(lin),2):
    ma = max(ma,lin[i]-lin[i-(k+1)*2+1])
print(ma)

Submission status: Wrong Answer

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

T='0'+S+'0'

ans,cnt=0,0
for i,(a,b) in enumerate(zip(S,S[1:])):
  if a=='0' and b=='1':
    cnt+=1
  elif cnt==k and a=='1' and b=='0':
    ans=max(ans,i+1)
    break
else:
  print(n)
  exit()
  
x,y=[],[]
for i,(a,b) in enumerate(zip(T,T[1:])):
  if a==b: continue
  if a=='0':
    x.append(i)
  else:
    y.append(i)
for a,b in zip(x,y[k:]):
  ans=max(ans,b-a)
print(ans)

Submission status: Wrong Answer

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

now=S[0]
cnt,c=[],1
if S[0]=='0': cnt.append(0)
for i in range(1,n):
  if now==S[i]:
    c+=1
  else:
    cnt.append(c)
    c=1
  now=S[i]
cnt.append(c)
if S[-1]=='0': cnt.append(0)
k=k*2 if S[0]=='0' else k*2+1
ans,tmp=sum(cnt[:k]),sum(cnt[:k])
for i in range(k,len(cnt)):
  tmp+=cnt[i]
  tmp-=cnt[i-(k)]
  ans=max(ans,tmp)
print(ans)

Submission status: Wrong Answer

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

now=S[0]
cnt,c=[],1
for i in range(1,n):
  if now==S[i]:
    c+=1
  else:
    cnt.append(c)
    c=1
  now=S[i]
cnt.append(c)
k=k*2 if S[0]=='0' else k*2+1
ans,tmp=sum(cnt[:k]),sum(cnt[:k])
for i in range(k,len(cnt)):
  tmp+=cnt[i]
  tmp-=cnt[i-(k)]
  ans=max(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,K = map(int,input().split())
S = input()
stands = []
temp = ''
first_handstand = False
for i,s in enumerate(S):
    if i == 0:
        temp += s
        continue
    if temp[-1] == s:
        temp += s
    else:
        stands.append(len(temp))
        temp = s
stands.append(len(temp)) # 最後の連続列
if S[0] == '0':
    stands.insert(0,0)
if S[-1] == '0':
    stands.append(0)
print(stands)


cumsum_stands = np.cumsum(np.array(stands))
cumsum_stands = np.insert(cumsum_stands,0,0)

ans = 0

for l in range(0,len(cumsum_stands),2):
    r = min(l + 2*K+1,len(cumsum_stands)-1)
    ans = max(ans, cumsum_stands[r] - cumsum_stands[l])
print(ans)

Submission status: Wrong Answer

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

offset = not (int(S[0]) ^ (K & 1))
runs = []

prev = S[0]
run = 0
for c in S:
    if c != prev:
        runs.append(run)
        run = 0
    prev = c
    run += 1
runs.append(run)

L = len(runs)
candidates = []

prev = sum(runs[max(0, offset - K): min(L, offset + K + 1)])
answer = prev

for i in range(offset + 2, L, 2):
    now = prev
    old_left = i - 2 - K
    new_right = i + K
    if old_left >= 0:
        now -= runs[old_left]
    if old_left + 1 >= 0:
        now -= runs[old_left + 1]
    if new_right - 1 < L:
        now += runs[new_right - 1]
    if new_right < L:
        now += runs[new_right]
    prev = now
    if answer > prev:
        answer = prev

print(answer)

Submission status: Wrong Answer

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

offset = int(S[0]) & (K & 1)
runs = []

prev = S[0]
run = 0
for c in S:
    if c != prev:
        runs.append(run)
        run = 0
    prev = c
    run += 1
runs.append(run)

L = len(runs)
candidates = []

prev = sum(runs[max(0, offset - K): min(L, offset + K + 1)])
candidates.append(prev)

for i in range(offset + 2, L, 2):
    now = prev
    old_left = i - 2 - K
    new_right = i + K
    if old_left >= 0:
        now -= runs[old_left]
    if old_left + 1 >= 0:
        now -= runs[old_left + 1]
    if new_right - 1 < L:
        now += runs[new_right - 1]
    if new_right < L:
        now += runs[new_right]
    prev = now
    candidates.append(prev)

print(max(candidates))

Submission status: Wrong Answer

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

t = list(map(int, list(s)))
lt = len(t)
w = []
sumw = []
u = 0
u1 = t[0]
ans1 = []
ans = 0
for i in range(lt):
    if t[i] == u1:
        u += 1
    if t[i] != u1:
        u = u if u1 == 1 else u*-1
        w.append(u)
        ans += abs(u)
        ans1.append(ans if u > 0 else ans*-1)
        u = 1
        u1 = 1 if u1 == 0 else 0

u = u if u1 == 1 else u*-1
w.append(u)
ans += abs(u)
ans1.append(ans if u > 0 else ans*-1)

ans2 = []
for i in range(len(ans1)):
    if i == 0:
        ans2.append(ans1[i])
    elif ans1[i] > 0:
        if i - 2*k - 1 >= 0:
            ans2.append(ans1[i] + ans1[i - 2*k - 1])
        else:
            ans2.append(ans1[i])
    else:
        if i - 2*k >= 0:
            ans2.append(ans1[i]*-1 + ans1[i - 2*k])
        else:
            ans2.append(ans1[i]*-1)

print(max(ans2))

Submission status: Wrong Answer

Solution code:
n, k = list(map(int, input().split()))
s = input()
#尺取り法
right = -1
left = -1
now_k = 0
while right + 1 < n and s[right + 1] == '1': 
    right += 1
#初めのrightの位置を決める
while now_k < k:
    now_k += 1
    while right + 1 < n and s[right + 1] == '0':
        right += 1
    while right + 1 < n and s[right + 1] == '1':
        right += 1
#今の時点で、rightがいい感じの場所にいる。
ans = (right - left + 1)
while right + 1 < n:
    while right + 1 < n and s[right + 1] == '0':
        right += 1
    while right + 1 < n and s[right + 1] == '1':
        right += 1
    while left + 1 < n and s[left + 1] == '1':
        left += 1
    while left + 1 < n and s[left + 1] == '0':
        left += 1
    left += 1
    ans = max(ans, right - left + 1)
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = list(map(int, input().split()))
s = input()
#尺取り法
right = -1
left = 0
now_k = 0
while right + 1 < n and s[right + 1] == '1': 
    right += 1
#初めのrightの位置を決める
while now_k < k:
    now_k += 1
    while right + 1 < n and s[right + 1] == '0':
        right += 1
    while right + 1 < n and s[right + 1] == '1':
        right += 1
#今の時点で、rightがいい感じの場所にいる。
ans = (right - left + 1)
while right + 1 < n:
    while right + 1 < n and s[right + 1] == '0':
        right += 1
    while right + 1 < n and s[right + 1] == '1':
        right += 1
    while left + 1 < n and s[left + 1] == '1':
        left += 1
    while left + 1 < n and s[left + 1] == '0':
        left += 1
    left += 1
    ans = max(ans, right - left +1)
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = list(map(int, input().split()))
s = input()
#尺取り法
right = 0
left = 0
now_k = 0
#初めのrightの位置を決める
while now_k < k:
    now_k += 1
    while right + 1 < n and s[right + 1] == '0':
        right += 1
    while right + 1< n and s[right + 1] == '1':
        right += 1
#今の時点で、rightがいい感じの場所にいる。
ans = (right - left + 1) 
while right + 1< n:
    while right + 1 < n and s[right + 1] == '0':
        right += 1
    while right + 1 < n and s[right + 1] == '1':
        right += 1
    while left + 1< n and s[left + 1] == '0':
        left += 1
    while left + 1 < n and s[left + 1] == '1':
        left += 1
    ans = max(ans, right - left +1)
print(ans)

Submission status: Wrong Answer

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

offset = int(S[0]) & (K & 1)
runs = []

prev = S[0]
run = 0
for c in S:
    if c != prev:
        runs.append(run)
        run = 0
    prev = c
    run += 1
runs.append(run)
runs.append(0)

L = len(runs)

# TODO 計算量削減
# inとoutのみを見ることでO(N^2) -> O(N)
print(max(sum(runs[max(0, i - K): min(L, i + K + 1)]) for i in range(offset, L, 2)))

Submission status: Wrong Answer

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

l = []
if s[0] == '0':
    l.append(0)

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

cum = [0]
for x in l:
    cum.append(cum[-1] + x)
# print(l)
# print(cum)
ans = max(l)
for i in range(0, n):
    #'1'
    if i % 2 == 0:
        r = i + 2 * k + 1
    #'0'
    else:
        r = i + 2 * k
    if r >= len(cum):
        break
    # print(cum[r] - cum[i])
    ans = max(ans, cum[r] - cum[i])


print(ans)

Submission status: Wrong Answer

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

l = []
if s[0] == '0':
    l.append(0)

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

cum = [0]
for x in l:
    cum.append(cum[-1] + x)
print(l)
print(cum)
ans = max(l)
for i in range(0, n):
    #'1'
    if i % 2 == 0:
        r = i + 2 * k + 1
    #'0'
    else:
        r = i + 2 * k
    if r >= len(cum):
        break
    print(cum[r] - cum[i])
    ans = max(ans, cum[r] - cum[i])


print(ans)

Submission status: Wrong Answer

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

l = []
if s[0] == '0':
    l.append(0)

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

cum = [0]
for x in l:
    cum.append(cum[-1] + x)
# print(l)
# print(cum)
ans = max(l)
for i in range(0, n):
    #'1'
    if i % 2 == 0:
        r = i + 2 * k + 1
    #'0'
    else:
        r = i + 2 + k
    if r >= len(cum):
        break
    # print(cum[r] - cum[i])
    ans = max(ans, cum[r] - cum[i])


print(ans)

Submission status: Wrong Answer

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

l = []
if s[0] == '0':
    l.append(0)

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

cum = [0]
for x in l:
    cum.append(cum[-1] + x)
# print(l)
# print(cum)
ans = max(l)
for i in range(0, n):
    r = i + 2 * k + 1
    if r >= len(cum):
        break
    # print(cum[r] - cum[i])
    ans = max(ans, cum[r] - cum[i])

print(ans)