Submission #8617148


Source Code Expand

Copy
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# (回数、インデックス)をheapで管理

from heapq import heappop, heappush

N,M = map(int,readline().split())
S = [x - ord('0') for x in read().rstrip()]

INF = 10 ** 18
dp_cnt = [INF] * (N+1)
dp_next = [0] * (N+1)

dp_cnt[N] = 0
q = [(0,N)]

for n in range(N-1,-1,-1):
    while True:
        cnt,ind = q[0]
        if ind > n + M:
            heappop(q)
            continue
        break
    cnt += 1
    if S[n] == 1:
        cnt = INF
        ind = 0
    dp_cnt[n] = cnt
    dp_next[n] = ind
    heappush(q, (cnt, n))

if dp_cnt[0] >= INF:
    print(-1)
    exit()

answer = []
append = answer.append
x = 0
while x != N:
    y = dp_next[x]
    append(y-x)
    x = y

print(' '.join(map(str,answer)))

Submission Info

Submission Time
Task F - Sugoroku
User maspy
Language Python (3.4.3)
Score 600
Code Size 877 Byte
Status AC
Exec Time 212 ms
Memory 19208 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 60
Set Name Test Cases
Sample 00-sample-00, 00-sample-01, 00-sample-02
All 00-sample-00, 00-sample-01, 00-sample-02, 01-handmade-03, 01-handmade-04, 01-handmade-05, 01-handmade-06, 01-handmade-07, 01-handmade-08, 01-handmade-09, 01-handmade-10, 02-random-11, 02-random-12, 02-random-13, 02-random-14, 02-random-15, 02-random-16, 02-random-17, 02-random-18, 02-random-19, 02-random-20, 02-random-21, 02-random-22, 02-random-23, 02-random-24, 02-random-25, 02-random-26, 02-random-27, 02-random-28, 02-random-29, 02-random-30, 02-random-31, 02-random-32, 02-random-33, 02-random-34, 02-random-35, 02-random-36, 02-random-37, 02-random-38, 02-random-39, 02-random-40, 02-random-41, 02-random-42, 02-random-43, 02-random-44, 02-random-45, 02-random-46, 02-random-47, 02-random-48, 02-random-49, 02-random-50, 02-random-51, 02-random-52, 02-random-53, 02-random-54, 02-random-55, 02-random-56, 02-random-57, 02-random-58, 02-random-59
Case Name Status Exec Time Memory
00-sample-00 AC 18 ms 3188 KB
00-sample-01 AC 18 ms 3064 KB
00-sample-02 AC 18 ms 3064 KB
01-handmade-03 AC 18 ms 3064 KB
01-handmade-04 AC 165 ms 8516 KB
01-handmade-05 AC 158 ms 9400 KB
01-handmade-06 AC 193 ms 15976 KB
01-handmade-07 AC 175 ms 15780 KB
01-handmade-08 AC 175 ms 11704 KB
01-handmade-09 AC 168 ms 19208 KB
01-handmade-10 AC 135 ms 12236 KB
02-random-11 AC 131 ms 14036 KB
02-random-12 AC 143 ms 12404 KB
02-random-13 AC 160 ms 5744 KB
02-random-14 AC 177 ms 7668 KB
02-random-15 AC 128 ms 13412 KB
02-random-16 AC 188 ms 10324 KB
02-random-17 AC 166 ms 6624 KB
02-random-18 AC 158 ms 7292 KB
02-random-19 AC 133 ms 14036 KB
02-random-20 AC 149 ms 8680 KB
02-random-21 AC 176 ms 9048 KB
02-random-22 AC 187 ms 8136 KB
02-random-23 AC 145 ms 14408 KB
02-random-24 AC 190 ms 9020 KB
02-random-25 AC 168 ms 7912 KB
02-random-26 AC 177 ms 9296 KB
02-random-27 AC 121 ms 13532 KB
02-random-28 AC 145 ms 8028 KB
02-random-29 AC 153 ms 8196 KB
02-random-30 AC 177 ms 9544 KB
02-random-31 AC 175 ms 15652 KB
02-random-32 AC 204 ms 8620 KB
02-random-33 AC 156 ms 9324 KB
02-random-34 AC 163 ms 9948 KB
02-random-35 AC 140 ms 14908 KB
02-random-36 AC 181 ms 13248 KB
02-random-37 AC 140 ms 10604 KB
02-random-38 AC 147 ms 10724 KB
02-random-39 AC 146 ms 11784 KB
02-random-40 AC 190 ms 7852 KB
02-random-41 AC 149 ms 10592 KB
02-random-42 AC 154 ms 11608 KB
02-random-43 AC 142 ms 15404 KB
02-random-44 AC 212 ms 10412 KB
02-random-45 AC 157 ms 12104 KB
02-random-46 AC 167 ms 12852 KB
02-random-47 AC 129 ms 14536 KB
02-random-48 AC 141 ms 6604 KB
02-random-49 AC 144 ms 12728 KB
02-random-50 AC 136 ms 11880 KB
02-random-51 AC 139 ms 14024 KB
02-random-52 AC 161 ms 15516 KB
02-random-53 AC 134 ms 12764 KB
02-random-54 AC 141 ms 14140 KB
02-random-55 AC 127 ms 13772 KB
02-random-56 AC 152 ms 14132 KB
02-random-57 AC 154 ms 15140 KB
02-random-58 AC 128 ms 13408 KB
02-random-59 AC 128 ms 14036 KB