結果

問題 No.78 クジ付きアイスバー
ユーザー yaoshimax
提出日時 2015-03-01 20:12:37
言語 Python2
(2.7.18)
結果
AC  
実行時間 12 ms / 5,000 ms
コード長 945 bytes
コンパイル時間 107 ms
コンパイル使用メモリ 7,040 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2024-11-08 00:29:09
合計ジャッジ時間 1,669 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

N,K=map(int,raw_input().split())
S=raw_input()
dp=[(0,0) for i in range(10*N+1)]
rest = 0
lstart=-1
lend=-1
for i in range(1,10*N+1):
    if rest==0:
        dp[i]=(dp[i-1][0]+1,rest)
    else:
        dp[i]=(dp[i-1][0],rest)
        rest-=1
    rest += ord(S[(i-1)%N])-ord("0")
    dp[i]=(dp[i][0],rest)
    if lstart == -1:
        for j in range(i-N,0,-N):
            if( dp[j][1]==dp[i][1] or dp[i][0]==dp[j][0] ):
                lstart=j
                lend=i
                #print i,"-",j
                break
if K <= 10*N:
    print dp[K][0]
else:
#if K >= lend:
    dif=(K-lend)
    interval=lend-lstart
    times = dif/interval
    base= times*(dp[lend][0]-dp[lstart][0])+dp[lend][0]
    startline = lend+times*interval
    rest= dp[lend][1]
    for i in range(startline+1,K+1):
        #print base,
        if rest == 0:
            base+=1
        else:
            rest-=1
        rest += ord(S[(i-1)%N])-ord("0")
    print base
0