結果
問題 |
No.1029 JJOOII 3
|
ユーザー |
![]() |
提出日時 | 2020-04-17 23:51:02 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 524 ms / 2,000 ms |
コード長 | 920 bytes |
コンパイル時間 | 286 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 78,976 KB |
最終ジャッジ日時 | 2024-10-03 16:14:06 |
合計ジャッジ時間 | 9,323 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines N, K = map(int, readline().split()) S = [] C = [] for _ in range(N): x, y = readline().split() x = tuple(0 if x == 'J' else 1 if x == 'O' else 2 for x in x.decode()) S.append(x) C.append(int(y)) INF = 10 ** 16 dp = [INF] * (K + K + K + 1) dp[0] = 0 cnt = [0] * (N * 3) for q in range(3): for i in range(N): cnt[3 * i + q] = sum(n == q for n in S[i]) def f(k, i): q, r = divmod(k, K) if r + cnt[3 * i + q] < K: return k + cnt[3 * i + q] for x in S[i]: if x == q: r += 1 if r == K: r = 0 q += 1 return K * q + r for k in range(K + K + K): for i in range(N): next_k = f(k, i) dp[next_k] = min(dp[k] + C[i], dp[next_k]) x = dp[-1] if x == INF: x = -1 print(x)