結果
問題 | 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]] += 1dpv = [-inf] * (k+1)dpw = [0] * (k+1)dpv[0] = 0dpw[0] = 1mod = 998244353for 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] % moddpw[i] %= modansv = max(dpv)print(ansv)answ = 0for i in range(k+1):if dpv[i] == ansv:answ += dpw[i]answ %= modprint(answ)