結果
問題 |
No.1029 JJOOII 3
|
ユーザー |
![]() |
提出日時 | 2020-04-17 22:21:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 664 ms / 2,000 ms |
コード長 | 3,002 bytes |
コンパイル時間 | 208 ms |
コンパイル使用メモリ | 82,424 KB |
実行使用メモリ | 83,956 KB |
最終ジャッジ日時 | 2024-10-03 13:49:52 |
合計ジャッジ時間 | 9,771 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
mod = 1000000007 eps = 10**-9 inf = 10**20 def main(): import sys input = sys.stdin.readline N, K = map(int, input().split()) S_list = [] C = [] for _ in range(N): S, c = input().split() S_list.append(S) C.append(int(c)) dp_J = [inf] * (K+1) dp_O = [inf] * (K+1) dp_I = [inf] * (K+1) dp_J[0] = 0 J_list = [] O_list = [] I_list = [] for S in S_list: J_list.append(S.count("J")) O_list.append(S.count("O")) I_list.append(S.count("I")) if sum(J_list) ==0 or sum(O_list) == 0 or sum(I_list) == 0: print(-1) exit() for i in range(K): for j in range(N): p = J_list[j] if not p: continue c = C[j] i_new = i+p if i_new < K: dp_J[i_new] = min(dp_J[i_new], dp_J[i] + c) else: cnt = K - i S = S_list[j] for k in range(len(S)): if S[k] == "J": cnt -= 1 if cnt == 0: kk = k break cnt = 0 flg = 0 for k in range(kk+1, len(S)): if S[k] == "O": cnt += 1 if cnt == K: flg = 1 kkk = k break if not flg: dp_O[cnt] = min(dp_O[cnt], dp_J[i] + c) else: cnt = 0 for k in range(kkk + 1, len(S)): if S[k] == "I": cnt += 1 if cnt == K: break dp_I[cnt] = min(dp_I[cnt], dp_J[i] + c) for i in range(K): for j in range(N): p = O_list[j] if not p: continue c = C[j] i_new = i+p if i_new < K: dp_O[i_new] = min(dp_O[i_new], dp_O[i] + c) else: cnt = K - i S = S_list[j] for k in range(len(S)): if S[k] == "O": cnt -= 1 if cnt == 0: kk = k break cnt = 0 for k in range(kk+1, len(S)): if S[k] == "I": cnt += 1 if cnt == K: break dp_I[cnt] = min(dp_I[cnt], dp_O[i] + c) for i in range(K): for j in range(N): p = I_list[j] if not p: continue c = C[j] i_new = min(i+p, K) dp_I[i_new] = min(dp_I[i_new], dp_I[i] + c) print(dp_I[-1]) if __name__ == '__main__': main()