結果
問題 | No.2378 Cards and Subsequences |
ユーザー |
|
提出日時 | 2023-07-10 13:57:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 386 ms / 2,000 ms |
コード長 | 1,296 bytes |
コンパイル時間 | 172 ms |
コンパイル使用メモリ | 82,144 KB |
実行使用メモリ | 140,300 KB |
最終ジャッジ日時 | 2024-09-12 23:40:32 |
合計ジャッジ時間 | 11,988 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 35 |
ソースコード
import sysinput = lambda :sys.stdin.readline()[:-1]ni = lambda :int(input())na = lambda :list(map(int,input().split()))yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")#######################################################################mod = 998244353n,m,k = na()s = [i-1 for i in na()]a = [i for i in na()]b = [i for i in na()]dp = [[0 for j in range(k+1)]for i in range(n+1)]dp[0][0] = 1f = [[-1 for j in range(m+1)] for i in range(n+1)]for i in range(n):for j in range(m):f[i+1][j] = f[i][j]f[i+1][s[i]] = ifor i in range(1, n+1):c = [0] * (k+1)for j in range(k+1):c[j] += dp[i-1][j]c[j] %= modif f[i-1][s[i-1]] != -1:for j in range(k+1):c[j] -= dp[f[i-1][s[i-1]]][j]c[j] %= mod#print(f[i-1][s[i-1]], i-1, c)for j in range(k+1):if j + a[s[i-1]] <= k:dp[i][j+a[s[i-1]]] += c[j]dp[i][j+a[s[i-1]]] %= modif j + b[s[i-1]] <= k:dp[i][j+b[s[i-1]]] += c[j]dp[i][j+b[s[i-1]]] %= modfor j in range(k+1):dp[i][j] += dp[i-1][j]dp[i][j] %= mod#print(*dp[i])print(dp[-1][-1])