結果

問題 No.1029 JJOOII 3
ユーザー tktk_snsntktk_snsn
提出日時 2020-12-31 22:26:44
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,341 bytes
コンパイル時間 302 ms
コンパイル使用メモリ 82,256 KB
実行使用メモリ 82,944 KB
最終ジャッジ日時 2024-10-09 22:32:56
合計ジャッジ時間 8,147 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

inf = 10 ** 18

N, K = map(int, input().split())
C = [-1] * N
J = [-1] * N
O = [-1] * N
I = [-1] * N
JO = [-1] * N
OI = [-1] * N

for i in range(N):
    si, ci = input().split()
    C[i] = int(ci)
    J[i] = si.count("J")
    O[i] = si.count("O")
    I[i] = si.count("I")

    jj = 0
    oo = O[i]
    tmp = [(0, oo)]
    for s in si:
        if s == "J":
            jj += 1
            tmp.append((jj, oo))
        if s == "O":
            oo -= 1
    JO[i] = tmp[:]

    oo = 0
    ii = I[i]
    tmp = [(0, ii)]
    for s in si:
        if s == "O":
            oo += 1
            tmp.append((oo, ii))
        if s == "I":
            ii -= 1
    OI[i] = tmp[:]


size = max(80, K)
dpJ = [inf] * (size + 1)
dpO = [inf] * (size + 1)
dpI = [inf] * (size + 1)
dpJ[0] = 0
for j, c in zip(J, C):
    for i in range(K):
        n = min(i+j, K)
        dpJ[n] = min(dpJ[n], dpJ[i] + c)

for jo, c in zip(JO, C):
    for a, b in jo:
        dpO[b] = min(dpO[b], dpJ[K-a] + c)

for j, c in zip(O, C):
    for i in range(K):
        n = min(i+j, K)
        dpO[n] = min(dpO[n], dpO[i] + c)

for oi, c in zip(OI, C):
    for a, b in oi:
        dpI[b] = min(dpI[b], dpO[K-a] + c)

for j, c in zip(I, C):
    for i in range(K):
        n = min(i+j, K)
        dpI[n] = min(dpI[n], dpI[i] + c)

if dpI[K] >= inf:
    print(-1)
else:
    print(dpI[K])
0