結果
問題 | No.2429 Happiest Tabehodai Ways |
ユーザー |
👑 ![]() |
提出日時 | 2023-08-19 03:53:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 89 ms / 2,000 ms |
コード長 | 973 bytes |
コンパイル時間 | 270 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 74,624 KB |
最終ジャッジ日時 | 2024-06-12 08:03:13 |
合計ジャッジ時間 | 3,811 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 44 |
ソースコード
"""ナップザックdp[]"""import sysfrom sys import stdinN,K = map(int,stdin.readline().split())C = list(map(int,stdin.readline().split()))D = list(map(int,stdin.readline().split()))assert 1 <= N <= 1000assert 1 <= K <= 1000for i in range(N):assert 1 <= C[i] <= 1000assert 1 <= D[i] <= 1000mod = 998244353dpmax = [float("-inf")] * (K+1)dpcnt = [0] * (K+1)dpmax[0] = 0dpcnt[0] = 1for csum in range(K+1):for c,d in zip(C,D):if csum+c <= K:nexc = csum+cnexd = dpmax[csum] + dif nexd > dpmax[nexc]:dpmax[nexc] = nexddpcnt[nexc] = 0if nexd == dpmax[nexc]:dpcnt[nexc] += dpcnt[csum]dpcnt[nexc] %= modans = [0,0]for i in range(K,-1,-1):if dpmax[i] > ans[0]:ans = [dpmax[i],0]if dpmax[i] == ans[0]:ans[1] += dpcnt[i]print (ans[0])print (ans[1] % mod)