Problem:


Score : 600 points

Problem Statement

Takahashi is playing a board game called Sugoroku.

On the board, there are N + 1 squares numbered 0 to N. Takahashi starts at Square 0, and he has to stop exactly at Square N to win the game.

The game uses a roulette with the M numbers from 1 to M. In each turn, Takahashi spins the roulette. If the number x comes up when he is at Square s, he moves to Square s+x. If this makes him go beyond Square N, he loses the game.

Additionally, some of the squares are Game Over Squares. He also loses the game if he stops at one of those squares. You are given a string S of length N + 1, representing which squares are Game Over Squares. For each i (0 \leq i \leq N), Square i is a Game Over Square if S[i] = 1 and not if S[i] = 0.

Find the sequence of numbers coming up in the roulette in which Takahashi can win the game in the fewest number of turns possible. If there are multiple such sequences, find the lexicographically smallest such sequence. If Takahashi cannot win the game, print -1.

Constraints

1 \leq N \leq 10^5

1 \leq M \leq 10^5

|S| = N + 1

S consists of 0 and 1.

S[0] = 0

S[N] = 0

Input

Input is given from Standard Input in the following format:

N M
S

Output

If Takahashi can win the game, print the lexicographically smallest sequence among the shortest sequences of numbers coming up in the roulette in which Takahashi can win the game, with spaces in between.

If Takahashi cannot win the game, print -1.

Sample Input 1

9 3
0001000100

Sample Output 1

1 3 2 3

If the numbers 1, 3, 2, 3 come up in this order, Takahashi can reach Square 9 via Square 1, 4, and 6. He cannot reach Square 9 in three or fewer turns, and this is the lexicographically smallest sequence in which he reaches Square 9 in four turns.

Sample Input 2

5 4
011110

Sample Output 2

-1

Takahashi cannot reach Square 5.

Sample Input 3

6 6
0101010

Sample Output 3

6



Sample input:
9 3
0001000100


Sample output:
1 3 2 3

Submission status: Wrong Answer

Solution code:
#gcdは3.4.3だとfractionsにある
from fractions import gcd
import math

from math import factorial as f

from math import ceil,floor,sqrt

from sys import exit

from copy import deepcopy
import numpy as np

import bisect
import re
import heapq


from copy import deepcopy
import itertools

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))



def main():
    n,m = mi()
    s = list(input())

    op = [0 for i in range(n+1)]

    cnt = 0
    flag = False
    place = []
    for i in range(len(s)):
        if flag and s[i] == '1':
            cnt+=1
            if cnt == m:
                print(-1)
                exit()
        elif s[i] == '1':
            flag = True
            cnt+=1
        else:
            place.append([])
            flag = False
            cnt = 0


    l = 0
    r = 0
    while r<n+1:
        if s[l] == '0':
            for i in range(r-l+1,m+1):
                if l+i > n:
                    break
                op[l+i] = i
            r = l+m
        l+=1
        print(l,r)
        





    ans = []
    op = op[::-1]
    np = 0
    flag = True
    while np < n:
        ans.append(op[np])
        np+=op[np]


    print(*ans[::-1])

    


        


main()

Submission status: Wrong Answer

Solution code:
def solve(mid):
    return c[ng]-c[mid]!=ng-mid
n,m=map(int,input().split())
*s,=map(int,input())
c=[0]+s[:]
for i in range(n):c[i+2]+=c[i+1]
a=[]
i=0
while i<=n:
    if n-i<=m:
        a+=n-i,
        break
    ok=i # 解が存在する値
    ng=i+m+1 # 解が存在しない値
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if solve(mid):
            ok=mid
        else:
            ng=mid
    a+=ok-i,
    if i==ok:
        print(-1)
        exit()
    i=ok
    #print(i)
print(*a)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
s=list(input())
s=list(map(int,s))
dp=[float("inf")]*(n+1)
dp[0]=0

for i in range(n-m+1):
    if s[i]:
        continue
    for j in range(1,m+1):
        if s[i+j]:
            continue
        dp[i+j]=min(dp[i]+1,dp[i+j])

if dp[n]==float("inf"):
    print(-1)
    exit()

ans=[]
c=0
now=0
k=dp[n]
for i in range(1,n+1):
    if c==k-1:
        ans.append(n-now)
        break

    if dp[i]==c+1:
        ans.append(i-now)
        c+=1
        now=i
        if c==k-1:
            ans.append(n-now)
            break



print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n-1):
        a,b=inpm()
        a-=1
        b-=1
        g[a].append((b,i))
        g[b].append((a,i))
    return n,g
    
def main():
    n,m=inpm()
    s=input()
    a=str(10**n)
    dp = ['0' for _ in range(n+1)]
    dp[0]='0'
    for i in range(n+1):
        if s[i]=='1':
            dp[n-i]=-1
    print(dp)
    for i in range(1,n+1):
        for j in range(max(0,i-m),i):
            if dp[i]==-1 or dp[j]==-1:
                continue
            x=i-j
            y=int(dp[j]+str(x))
            y=str(y)
            if dp[i]=='0':
                dp[i]=y
            elif len(dp[i])==len(y):
                dp[i]=str(max(int(dp[i]),int(y)))
            elif len(dp[i])>len(y):
                dp[i]=y
            elif len(dp[i])<len(y):
                continue
    print(dp)
    if int(dp[n])==0:
        print(-1)
    else:
        ans = list(dp[n])
        ans.reverse()
        print(' '.join(ans))
    


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
S = input()
p = 0
ans = []
while p != N:
    hoge = 0
    for i in range(min(M,N-p),0,-1):
        if S[p + i] == '0':
            hoge = i
            break
    p += hoge
    if hoge == 0:
        print(-1)
        exit()
    ans.append(hoge)
print(*ans)

Submission status: Wrong Answer

Solution code:
def solve(mid):
    return c[ok]-c[mid]!=ok-mid
n,m=map(int,input().split())
*s,=map(int,input())
c=s[:]
for i in range(n-1):c[i+1]+=c[i]
a=[]
i=0
while i<=n:
    if n-i<=m:
        a+=n-i,
        break
    ok=i # 解が存在する値
    ng=i+m+1 # 解が存在しない値
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if solve(mid):
            ok=mid
        else:
            ng=mid
    a+=ok-i,
    if i==ok:
        print(-1)
        exit()
    i=ok
    #print(i)
print(*a)

Submission status: Wrong Answer

Solution code:
def solve(mid):
    return c[ok]-c[mid]!=ok-mid
n,m=map(int,input().split())
*s,=map(int,input())
c=s[:]
for i in range(n-1):c[i+1]+=c[i]
a=[]
i=0
while i<=n:
    if n-i<=m:
        a+=n-i,
        break
    ok=i # 解が存在する値
    ng=i+m+1 # 解が存在しない値
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if solve(mid):
            ok=mid
        else:
            ng=mid
    a+=ok-i,
    if i==ok:
        print(-1)
        exit()
    i=ok
    print(i)
print(*a)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline

N, M = map(int, input().split())
S = list(input())[: -1]
x = 0
res = []
s = []
for i in range(N + 1):
  if S[i] == "0": s.append(i)
#print(s)
for _ in range(N):
  if x == N:
    break
  n = bl(s, x + M)
  #print(n)
  if n >= len(s):
    res.append(N - x)
    x = N
    break
  if s[n] > x + M:
    n = max(0, n - 1)
  res.append(s[n] - x)
  x = s[n]
if x != N: print(-1)
else:
  print(" ".join(list(map(str, res))))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
s=list(input())
s=list(map(int,s))
dp=[float("inf")]*(n+1)
dp[0]=0

for i in range(n-m+1):
    if s[i]:
        continue
    for j in range(1,m+1):
        if s[i+j]:
            continue
        dp[i+j]=min(dp[i]+1,dp[i+j])

if dp[n]==float("inf"):
    print(-1)
    exit()

ans=[]
while n!=0:
    for i in range(m,0,-1):
        if dp[n-i]==dp[n]-1:
            ans.append(i)
            n-=i
ans.reverse()
print(*ans)

Submission status: Wrong Answer

Solution code:
n,m=[int(j) for j in input().split()]
s=input()
l=[]
for i in range(n+1):
    if s[i]=="0":
        l.append(i)
import bisect
ans=[]
c=0
while True:
    if c+m>=n:
        ans.append(n-c)
        break
    p=bisect.bisect_right(l,c+m)-1
    ans.append(l[p]-c)
    if l[p]-c==0:
        print(-1)
        exit()
    c=l[p]
    if c==n:
        break
print(*ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
s=input()
ans=""
p=n
while p!=0:
	flag=False
	h=0
	if p<m:
		h=m-p
	for i in range(min(m,p)):
		if s[p-m+i+h]=="0":
			p=p-m+i+h
			ans+=str(m-i-h)
			flag=True
			break
	if flag==False:
		print(-1)
		exit()
qq=[]
for i in range(len(ans)):
	qq.append(ans[-i-1])
print(*qq)

Submission status: Wrong Answer

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

S = tuple(map(lambda x: x == '0', input()))

dp = [N*N]*(N+1)
dp[-1] = 0

for i in reversed(range(N)):
    if S[i]:
        dp[i] = min(dp[i+1:min(N+1,i+M+1)])+1
if dp[0] >= N*N:
    print(-1)
    exit()

dp += [N*N]*(M+1)
res = []
i = 0
while i < N:
    t = dp[i]
    s = min(k for k in range(1,M+1) if dp[i+k]==t-1)
    res.append(s)
    i += s
print(*res)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
S = list(input())
S = [int(s) for s in S]
S.reverse()
dp = [-1 for i in range(N+1)]
dp[0] = 0
for i in range(1, M+1):
	if i > N:
		break
	if S[i] == 0:
		dp[i] = 1

undetermined = M+1
for i in range(1, N):
	if S[i] == 1:
		continue
	for j in range(undetermined, i+M+1):
		if j <= N and S[j] == 0:
			dp[j] = dp[i] + 1
			undetermined = j+1
if dp[N] == -1:
	print(-1)
	exit()

ans = []
prev = (dp[N], N)
for i in range(N-1, -1, -1):
	if dp[i] == -1 or prev[0] == dp[i]:
		continue
	else:
		ans.append(str(prev[1] - i))
		prev = (dp[i], i)

print(" ".join(ans))

Submission status: Wrong Answer

Solution code:
n, m = [int(x) for x in input().split()]

s = input()
c = n + 1

h = []
while True:
	d = m
	while d > 0:
		if c - d > 0:
			if s[c - d] == '0':
				break
		d -= 1
	
    
	print(h)
	print(c)
	if d == 0:
		print(-1)
		break
        
        
        
	c -= d
	h.append(d)
	if c == 0:
		h.reverse()
		print(h)
		print(" ".join(h))
		break

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
l = list(map(int,list(input()[::-1])))
safe = [-1]*(n+1)
r = n
for i in range(n,-1,-1):
    if l[i]:
        continue
    if r-i > m:
        r -= 1
        while l[r]:
            r -= 1
        if r == i:
            print(-1)
            exit()
    safe[i] = r
dice = list()
cur = 0
while cur < n:
    dice.append(safe[cur]-cur)
    cur = safe[cur]
print(" ".join(map(str,dice[::-1])))

Submission status: Wrong Answer

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

D = []
t = N
while t > 0:
  print(t)
  if t - M <= 0:
    D.append(t)
    break
  for i in range(M, 0, -1):
    if S[t - i] == "0":
      D.append(i)
      t -= i
      break
  else:
    print(-1)
    exit()

for i in range(len(D) -1, -1, -1):
  print(D[i],end = " ")

Submission status: Wrong Answer

Solution code:
a,b=map(int,input().split())
masu=list(map(int,input()[::-1]))
i=0
de=[]
e=1
if masu[0]==1:
  print(-1)
elif masu[-1]:
  print(-1)
else:
  while i<a:
      if 0 not in masu[i+1:i+b+1]:
        print(-1)
        e=0
        break
      else:
        if len(masu)-i<=b:i=a;de+=[len(masu)-i]
        else:
          de+=[b-masu[i+1:i+b+1][::-1].index(0)]
          i+=de[-1]
if e:print(' '.join(map(str,de[::-1])))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
S = input()
if N <= M:
  print(N)
  exit()
if '1'*M in S:
  print(-1)
  exit()
count = [0 for _ in range(N+1)]
for k in range(M+1):
  if S[k] == '1':
    count[k] = -1
  else:
    count[k] = k
from collections import deque
now = M
while now < N:
  now += 1
  cnt = 0 
  before = deque(count[now-M:now])
  a = before.popleft()
  if S[now] == '1':
    count[now] = -1
    continue
  else:
    if a > 0:
      count[now] = M
    else:
      while a  < 0:
        cnt += 1
        a = before.popleft()
      count[now] = M - cnt

c = 0
ans = ''
while c < N:
  ans = str(count[-1-c]) + ' ' + ans
  c += count[-1-c]

print(ans)

Submission status: Time Limit Exceeded

Solution code:

class SegmentTree:
    def __init__(self, size, fn=min, default=None, initial_values=None):
        """
        :param int size:
        :param callable fn: 区間に適用する関数。引数を 2 つ取る。min, max, operator.xor など
        :param default:
        :param list initial_values:
        """
        default = default or 0

        # size 以上である最小の 2 冪を size とする
        n = 1
        while n < size:
            n *= 2
        self._size = n
        self._fn = fn

        self._tree = [default] * (self._size * 2 - 1)
        if initial_values:
            i = self._size - 1
            for v in initial_values:
                self._tree[i] = v
                i += 1
            i = self._size - 2
            while i >= 0:
                self._tree[i] = self._fn(self._tree[i * 2 + 1], self._tree[i * 2 + 2])
                i -= 1

    def set(self, i, value):
        """
        i 番目に value を設定
        :param int i:
        :param value:
        :return:
        """
        x = self._size - 1 + i
        self._tree[x] = value

        while x > 0:
            x = (x - 1) // 2
            self._tree[x] = self._fn(self._tree[x * 2 + 1], self._tree[x * 2 + 2])

    def update(self, i, value):
        """
        もとの i 番目と value に fn を適用したものを i 番目に設定
        :param int i:
        :param value:
        :return:
        """
        x = self._size - 1 + i
        self.set(i, self._fn(self._tree[x], value))

    def get(self, from_i, to_i=None, k=0, L=None, r=None):
        """
        [from_i, to_i) に fn を適用した結果を返す
        :param int from_i:
        :param int to_i:
        :param int k: self._tree[k] が、[L, r) に fn を適用した結果を持つ
        :param int L:
        :param int r:
        :return:
        """
        if to_i is None:
            return self._tree[self._size - 1 + from_i]

        L = 0 if L is None else L
        r = self._size if r is None else r

        if from_i <= L and r <= to_i:
            return self._tree[k]

        if to_i <= L or r <= from_i:
            return None

        ret_L = self.get(from_i, to_i, k * 2 + 1, L, (L + r) // 2)
        ret_r = self.get(from_i, to_i, k * 2 + 2, (L + r) // 2, r)
        if ret_L is None:
            return ret_r
        if ret_r is None:
            return ret_L
        return self._fn(ret_L, ret_r)

    def __len__(self):
        return self._size


def resolve():
    INF = float('inf')
    N, M = map(int, input().split())
    S = input()

    dp = [INF] * (N + 1)
    dp[0] = 0

    seg = SegmentTree(N + 1, min, INF)
    seg.update(N, 0)
    for i in range(N - 1, -1, -1):
        if S[i] == '1':
            continue
        # seg.query(l, r) := [l, r)の最小値
        dp[i] = seg.get(i, i + M + 1) + 1
        seg.update(i, dp[i])

    ans = []
    position = 0
    while position < N:
        for move in range(1, M + 1):
            if position + move > N:
                continue
            if S[position + move] == '1':
                continue

            # 最短手数にならない
            if dp[position + move] == dp[position]:
                continue

            ans.append(move)
            position += move
            break

        else:
            print(-1)
            return

    print(*ans)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M = map(int, input().split())
S = input() # len(S)=S+1 !!!
A = [-1 for _ in range(N+1)]
S = S[::-1]
for i in range(N+1):
  if S[i] == "1":
    continue
  flg = True
  for m in range(1,M+1):
    if i + m > N:
      A[i] = N
      flg = False
      break
    if S[i+m] == "0":
      A[i] = i+m
      flg = False
    else:
      continue
  if flg:
    print(-1)
    exit(0)
#print(A)
i = 0
ANS = []
while i < N :
  nxt = A[i]
  ANS.append(nxt - i)
  i = nxt
  
print(" ".join(map(str,ANS[::-1])))

Submission status: Time Limit Exceeded

Solution code:
# F - Sugoroku
import sys
sys.setrecursionlimit(10 ** 9)

n,m = map(int,input().split())
s = input()

r = []
mnr = [m for _ in range(n+1)]
mnl = n+1
def dfs(x,c):
  global mnr,mnl
  #print(x,c)
  if x == n:
    #print(r)
    if len(r) < mnl or (len(r) == mnl and r < mnr):
      mnr = r[:]
      mnl = len(r)
    return True
  if c >= mnl or x > n or s[x] == '1':
    return False
  for i in range(m,0,-1):
    r.append(i)
    dfs(x+i,c+1)
    r.pop()
dfs(0,0)
if mnl < n+1:
  print(*mnr)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m = map(int, readline().split())
    s = input()
    dp1 = [INF] * (n + 1)
    dp1[0] = 0

    for i in range(n):
        for j in range(1, m + 1):
            if i + j > n:
                break
            if s[i + j] == "0":
                dp1[i + j] = min(dp1[i + j], dp1[i] + 1)

    dp2 = [-INF] * (n + 1)
    dp2[0] = dp1[n]
    t = s[::-1]

    for i in range(n):
        for j in range(1, m + 1):
            if i + j > n:
                break
            if t[i + j] == "0":
                dp2[i + j] = max(dp2[i + j], dp2[i] - 1)
    dp2 = dp2[::-1]
    if dp1[n] != INF:
        res = []
        i = 0
        p = 0
        cnt = 0
        while i < n:
            i += 1
            if dp2[i] == cnt + 1:
                res.append(i-p)
                p = i
                cnt += 1
        print(*res)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc146/tasks/abc146_f
# F - Sugoroku

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

dp=[float("inf")]*(N+1)
dp[0]=0

for i in range(1,N+1):
    if S[i]=="1":
        pass
    else:
        for j in range(1,M+1):
            if i>=j:
                if S[i-j]=="0":
                    tmp= dp[i-j]+1
                    dp[i]=min(tmp,dp[-1])
                    
if dp[-1]==float("inf"):
    print(-1)
else:
    maxi=dp[-1]
    L=[ [] for _ in range(maxi+1)]
    for i,num in enumerate(dp):
        if num!=float("inf"):
            L[num].append(i)

    t = maxi
    ans_list=[N]
   
    for i in range(maxi):
        for num in L[t-1]:
            if 1<= ans_list[-1] - num <= M:
                ans_list.append(num)
                t -=1
                break
                
    fin=ans_list[::-1]
    final_ans=[]
    for j in range(1,maxi+1):
        final_ans.append(fin[j]-fin[j-1])
    print(*final_ans)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc146/tasks/abc146_f
# F - Sugoroku

def search(a,x,ans):
    if x==0:
        #ans_list.append(ans)
        final=ans[::-1]
        ret=[]
        for i in range(1,maxi+1):
            ret.append(final[i]-final[i-1])
        print(*ret)
        sys.exit()
    else:
        target=L[x-1]
        for p in target:
            if a-p<=M:
                ret=search(p,x-1,ans+[p])                

import sys
N,M = map(int,input().split())
S=list(input())
#print(S)

dp=[float("inf")]*(N+1)
dp[0]=0

for i in range(1,N+1):
    if S[i]=="1":
        pass
    else:
        for j in range(1,M+1):
            if i>=j:
                if S[i-j]=="0":
                    tmp= dp[i-j]+1
                    dp[i]=min(tmp,dp[-1])
#print(dp)
if dp[-1]==float("inf"):
    print(-1)
else:
    maxi=dp[-1]
    L=[ [] for _ in range(maxi+1)]
    for i,num in enumerate(dp):
        if num!=float("inf"):
            L[num].append(i)

    t = maxi
    ans_list=[N]
    #print(L)
    #print(t,ans_list)
   
    for i in range(maxi):
        for num in L[t-1]:
            if 1<= ans_list[-1] - num <= M:
                ans_list.append(num)
                t -=1
                break
    #print(ans_list)
    fin=ans_list[::-1]
    final_ans=[]
    for j in range(1,maxi+1):
        final_ans.append(fin[j]-fin[j-1])
    print(*final_ans)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc146/tasks/abc146_f
# F - Sugoroku

def search(a,x,ans):
    if x==0:
        #ans_list.append(ans)
        final=ans[::-1]
        ret=[]
        for i in range(1,maxi+1):
            ret.append(final[i]-final[i-1])
        print(*ret)
        sys.exit()
    else:
        target=L[x-1]
        for p in target:
            if a-p<=M:
                ret=search(p,x-1,ans+[p])                

import sys
N,M = map(int,input().split())
S=list(input())
#print(S)

dp=[float("inf")]*(N+1)
dp[0]=0

for i in range(1,N+1):
    if S[i]=="1":
        pass
    else:
        for j in range(1,M+1):
            if i>=j:
                if S[i-j]=="0":
                    tmp= dp[i-j]+1
                    dp[i]=min(tmp,dp[-1])
#print(dp)
if dp[-1]==float("inf"):
    print(-1)
else:
    maxi=dp[-1]
    L=[ [] for _ in range(maxi+1)]
    for i,num in enumerate(dp):
        if num!=float("inf"):
            L[num].append(i)

    t = maxi
    ans_list=[N]
    #print(L)
    #print(t,ans_list)
   
    for i in range(maxi):
        for num in L[t-1]:
            if 1<= ans_list[-1] - num <= M:
                ans_list.append(num)
                t -=1
                break
    #print(ans_list)
    fin=ans_list[::-1]
    final_ans=[]
    for j in range(1,maxi+1):
        final_ans.append(fin[j]-fin[j-1])
    print(*final_ans)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc146/tasks/abc146_f
# F - Sugoroku

def search(a,x,ans):
    if x==0:
        #ans_list.append(ans)
        final=ans[::-1]
        ret=[]
        for i in range(1,maxi+1):
            ret.append(final[i]-final[i-1])
        print(*ret)
        sys.exit()
    else:
        target=L[x-1]
        for p in target:
            if a-p<=M:
                ret=search(p,x-1,ans+[p])                

import sys
sys.setrecursionlimit(10**9)
N,M = map(int,input().split())
S=list(input())
#print(S)

dp=[float("inf")]*(N+1)
dp[0]=0

for i in range(1,N+1):
    if S[i]=="1":
        pass
    else:
        for j in range(1,M+1):
            if i>=j:
                if S[i-j]=="0":
                    tmp= dp[i-j]+1
                    dp[i]=min(tmp,dp[-1])
#print(dp)
if dp[-1]==float("inf"):
    print(-1)
else:
    ans_list=[]
    maxi=dp[-1]
    L=[ [] for _ in range(maxi+1)]
    for i,num in enumerate(dp):
        if num!=float("inf"):
            L[num].append(i)
    #print(L)
    search(N,maxi,[N])
    #print(ans_list)

Submission status: Time Limit Exceeded

Solution code:
import sys
#import numpy as np
#from collections import defaultdict
#import math
#from collections import deque




def main():
    N ,M = map(int,input().split())
    S = list(str(input()))
    p =N
    act = 0
    ans =[]
    while True:
        if p <=M:
            ans.append(p)
            break

        for i in range(M,0,-1):
            if S[p - i] =="1":
                continue
            else:
                p = p-i
                act +=1
                ans.append(i)
                break
        if i ==0:
            print(-1)
            exit()



    for l in reversed(ans):
        print(l,sep="",end=" ")









if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo


@mt
def slv(N, M, S):

    from functools import lru_cache
    @lru_cache(maxsize=None)
    def dfs(x):
        if x == 0:
            return []

        for i in range(M, 0, -1):
            if 0 <= x-i and S[x-i] == '0':
                r = dfs(x-i)
                if r is not None:
                    r.append(i)
                    return r
        return None
    ans = dfs(N)
    if ans is None:
        ans = [-1]
    return ans




def main():
    N, M = read_int_n()
    S = read_str()
    print(*slv(N, M, S))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

dp=[[] for _ in range(N+1)]
dp[0]=(0,[])
for i in range(1,N+1):
  if S[i]==0:
    cand=[]
    for j in range(1,M+1):
      if i-j<0:
        break
      elif S[i-j]==1:
        continue
        
      if dp[i-j]:
        cand.append((dp[i-j][0]+1,dp[i-j][1]+[j]))
    cand.sort()
    #print(i,cand)
    if cand:
      dp[i]=cand[0]
    
#print(dp)
if dp[-1]:
  print(*dp[-1][1])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int, input().split())
S=input()
now=S[N-1]
dp=[float("INF")]*(N+1)
dp[N]=0
for i in range(N-1,-1,-1):
    if S[i]=="1":
        continue
    else:
        dp[i]=1+min(dp[i+1:i+1+M])
#print(dp)
#print(dp[0])
now=dp[0]
nowi=0
if now==float("INF"):
    print(-1)
    exit()
for i in range(1,N+1):
    if now>dp[i]:
        print(i-nowi, end=" ")
        now=dp[i]
        nowi=i

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq

def main():
  input = sys.stdin.readline
  n, m = map(int, input().split())
  s = input()
  
  inf = pow(10, 6)
  ans = [inf]*(n+1)
  key = []
  heapq.heapify(key)
  heapq.heappush(key, (0, n))
  ans[n] = 0
  index = n-1
  while key:
    sub = heapq.heappop(key)
    s1, s2 = sub[0], sub[1]
    subindex = s2
    for i in range(min([index, s2-1]), max([-1, s2-m-1]), -1):
      if ans[i] != inf:
        continue
      if s[i] == "1":
        continue
      heapq.heappush(key, (s1+1, i))
      ans[i] = s2
      subindex = i
    index = subindex
      
  
  if ans[0] == inf:
    print(-1)
  else:
    index = 0
    answer = []
    while True:
      subindex = ans[index]
      answer.append(subindex-index)
      if subindex == n:
        break
      index = subindex
    print(*answer)
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq

def main():
  input = sys.stdin.readline
  n, m = map(int, input().split())
  s = input()
  
  inf = pow(10, 6)
  ans = [inf]*(n+1)
  key = []
  heapq.heapify(key)
  heapq.heappush(key, (0, n))
  ans[n] = 0
  index = n-1
  while key:
    sub = heapq.heappop(key)
    s1, s2 = sub[0], sub[1]
    subindex = s2
    for i in range(min([index, s2-1]), max([-1, s2-m-1]), -1):
      if ans[i] != inf:
        continue
      if s[i] == "1":
        continue
      heapq.heappush(key, (s1+1, i))
      ans[i] = s2
      subindex = i
    index = subindex
      
  
  if ans[0] == inf:
    print(-1)
  else:
    index = 0
    answer = []
    while True:
      subindex = ans[index]
      answer.append(subindex-index)
      if subindex == n:
        break
      index = subindex
  
    print(*answer)
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq

def main():
  input = sys.stdin.readline
  n, m = map(int, input().split())
  s = input()
  
  inf = pow(10, 6)
  ans = [inf]*(n+1)
  key = []
  heapq.heapify(key)
  heapq.heappush(key, (0, n))
  ans[n] = 0
  index = n-1
  while key:
    sub = heapq.heappop(key)
    s1, s2 = sub[0], sub[1]
    for i in range(min([index, s2-1]), max([-1, s2-m-1]), -1):
      if ans[i] != inf:
        continue
      if s[i] == "1":
        continue
      heapq.heappush(key, (s1+1, i))
      ans[i] = s2
  
  if ans[0] == inf:
    print(-1)
  else:
    index = 0
    answer = []
    while True:
      subindex = ans[index]
      answer.append(subindex-index)
      if subindex == n:
        break
      index = subindex
  
    print(*answer)
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
s = input()
dp = [-1 for _i in range(n+1)]
dp[0] = 0
for i in range(1, n+1):
    if i <= m:
        if s[i]=="0":
            dp[i] = 0
        continue
    for j in range(max(0,i-m), i):
        if s[j]=="0" and dp[j] >= 0:
            dp[i] = j
            break


if dp[n] >= 0:
    r = []
    p = n
    while p > 0:
        nex = dp[p]
        r.append(p-nex)
        p = nex
    print(*r[::-1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
s = input()
dp = [-1 for _i in range(n+1)]
dp[0] = 0
for i in range(1, n+1):
    if i <= m:
        if s[i]=="0":
            dp[i] = 0
        continue
    for j in range(i-1, max(0,i-m)-1, -1):
        if s[j]=="0" and dp[j] >= 0:
            dp[i] = j


if dp[n] >= 0:
    r = []
    p = n
    while p > 0:
        nex = dp[p]
        r.append(p-nex)
        p = nex
    print(*r[::-1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
s = input()
dp = [[-1, float("inf")] for _i in range(n+1)]
dp[0] = [0,0]
for i in range(1, n+1):
    if i <= m:
        if s[i]=="0":
            dp[i] = [0, 1]
        continue
    for j in range(max(0,i-m), i):
        if s[j]=="0" and dp[j][0] >= 0:
            if dp[i][1] > dp[j][1]+1:
                dp[i][0] = j
                dp[i][1] = dp[j][1] + 1 
            elif dp[i][1] == dp[j][1]+1:
                dp[i][0] = min(dp[i][0], j)

if dp[n][0] >= 0:
    r = []
    p = n
    while p > 0:
        nex = dp[p][0]
        r.append(p-nex)
        p = nex
    print(*r[::-1])
else:
    print(-1)