結果
問題 | No.1818 6 Operations |
ユーザー |
|
提出日時 | 2024-11-18 01:22:27 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 509 ms / 2,500 ms |
コード長 | 546 bytes |
コンパイル時間 | 250 ms |
コンパイル使用メモリ | 82,316 KB |
実行使用メモリ | 182,708 KB |
最終ジャッジ日時 | 2024-11-18 01:22:39 |
合計ジャッジ時間 | 10,818 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
N, M = map(int, input().split()) A = list(map(int, input().split())) B = list(map(int, input().split())) def f(data): res = [] for a in data: res.append(0) res += [1] * a return res A = f(A) B = f(B) N = len(A) M = len(B) INF = 10**18 dp = [[INF]*(M+1) for _ in range(N+1)] dp[0][0] = 0 for i, ai in enumerate(A, start=1): for j, bj in enumerate(B, start=1): cost = int(ai != bj) dp[i][j] = min( dp[i][j], dp[i-1][j-1]+cost, dp[i][j-1]+1, dp[i-1][j]+1 ) print(dp[-1][-1])