結果
問題 | No.2429 Happiest Tabehodai Ways |
ユーザー |
|
提出日時 | 2023-08-11 20:40:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 93 ms / 2,000 ms |
コード長 | 796 bytes |
コンパイル時間 | 319 ms |
コンパイル使用メモリ | 82,188 KB |
実行使用メモリ | 77,080 KB |
最終ジャッジ日時 | 2024-06-12 07:55:57 |
合計ジャッジ時間 | 4,132 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 44 |
ソースコード
n, k = map(int, input().split()) c = list(map(int, input().split())) d = list(map(int, input().split())) inf = float("inf") fv = [-inf for i in range(k+1)] fw = [0 for i in range(k+1)] for i in range(n): if c[i] <= k: fv[c[i]] = max(fv[c[i]], d[i]) for i in range(n): if c[i] <= k and fv[c[i]] == d[i]: fw[c[i]] += 1 dpv = [-inf] * (k+1) dpw = [0] * (k+1) dpv[0] = 0 dpw[0] = 1 mod = 998244353 for i in range(1, k+1): for j in range(1, i+1): dpv[i] = max(dpv[i], dpv[i-j] + fv[j]) for j in range(1, i+1): if dpv[i] == fv[j] + dpv[i-j]: dpw[i] += dpw[i-j] * fw[j] % mod dpw[i] %= mod ansv = max(dpv) print(ansv) answ = 0 for i in range(k+1): if dpv[i] == ansv: answ += dpw[i] answ %= mod print(answ)