結果

問題 No.1029 JJOOII 3
ユーザー tktk_snsn
提出日時 2020-12-31 18:01:47
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,278 bytes
コンパイル時間 552 ms
コンパイル使用メモリ 82,452 KB
実行使用メモリ 77,296 KB
最終ジャッジ日時 2024-10-09 17:08:22
合計ジャッジ時間 7,167 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12 WA * 17 RE * 9
権限があれば一括ダウンロードができます

ソースコード

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[:]
    

dpJ = [inf] * (K + 1)
dpO = [inf] * (K + 1)
dpI = [inf] * (K + 1)
dpJ[0] = 0
for j, c in zip(J, C):
    for i in range(K - j + 1):
        dpJ[i+j] = min(dpJ[i+j], 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 - j + 1):
        dpO[i+j] = min(dpO[i+j], 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 - j + 1):
        dpI[i+j] = min(dpI[i+j], dpI[i] + c)

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