結果
問題 | No.2378 Cards and Subsequences |
ユーザー |
|
提出日時 | 2023-07-07 23:10:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 291 ms / 2,000 ms |
コード長 | 853 bytes |
コンパイル時間 | 252 ms |
コンパイル使用メモリ | 82,220 KB |
実行使用メモリ | 136,300 KB |
最終ジャッジ日時 | 2024-07-21 19:34:45 |
合計ジャッジ時間 | 9,570 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 35 |
ソースコード
MOD = 998244353N, M, K = map(int, input().split())S = list(map(lambda x: x - 1, map(int, input().split())))A = list(map(int, input().split()))B = list(map(int, input().split()))prev = dict()ac = [[0] * (K + 1) for _ in range(N + 1)]dp = [[0] * (K + 1) for _ in range(N)]for i in range(N):p = 0a = A[S[i]]b = B[S[i]]if S[i] in prev:p = prev[S[i]]else:dp[i][a] += 1dp[i][b] += 1prev[S[i]] = ifor j in range(K + 1):if j + a <= K:dp[i][j + a] += ac[i][j] - ac[p][j]dp[i][j + a] %= MODif j + b <= K:dp[i][j + b] += ac[i][j] - ac[p][j]dp[i][j + b] %= MODfor j in range(K + 1):ac[i + 1][j] = ac[i][j] + dp[i][j]ac[i + 1][j] %= MOD# for i in range(N + 1):# print(ac[i])print(ac[-1][K])