Submission #36481667

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from collections import deque
N,K = map(int, input().split())
S = list(input())
# Sを0/1の連続個数に変換する
cnt = 1
before = S[0]
conv_S = deque()            # 0/1が何連続しているか
is_handstand_deq = deque()  # 初期で逆立ちしているか
for i in range(1,N):
    if S[i] == before:
        cnt += 1
    else:
        conv_S.append(cnt)
        is_handstand_deq.append(before)
        cnt = 1
        before = S[i]
conv_S.append(cnt)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

from collections import deque

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

# Sを0/1の連続個数に変換する
cnt = 1
before = S[0]
conv_S = deque()            # 0/1が何連続しているか
is_handstand_deq = deque()  # 初期で逆立ちしているか

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

conv_S.append(cnt)
is_handstand_deq.append(before)

ans = 0

section = deque()   # 注目する人の並び
section_sum = 0     # 上記内での合計人数
remain_order = K    # 指示できる残り回数

while len(conv_S) != 0:

    if is_handstand_deq[0] == "1":
        # 逆立している人は無条件に加えてOK
        person_cnt = conv_S.popleft()
        is_handstand = is_handstand_deq.popleft()

        section.append((person_cnt,is_handstand))
        section_sum += person_cnt

    elif is_handstand_deq[0] == "0":
        # 直立している人には指示が必要
        if remain_order == 0:
            # 指示できる回数が0だったら、指示回数を回復するまで左端の方を繰り出す
            while len(section) != 0:
                person_cnt,is_handstand = section.popleft()
                section_sum -= person_cnt

                if is_handstand == "0":
                    remain_order += 1
                    break
        
        person_cnt = conv_S.popleft()
        is_handstand = is_handstand_deq.popleft()
        
        section.append((person_cnt,is_handstand))
        remain_order -= 1
        section_sum += person_cnt
    
    ans = max(ans,section_sum)

print(ans)

Submission Info

Judge Result