結果
問題 | No.2429 Happiest Tabehodai Ways |
ユーザー |
|
提出日時 | 2023-08-18 23:20:00 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 327 ms / 2,000 ms |
コード長 | 554 bytes |
コンパイル時間 | 248 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 77,056 KB |
最終ジャッジ日時 | 2024-06-12 08:02:26 |
合計ジャッジ時間 | 4,092 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 44 |
ソースコード
from collections import defaultdictmod=998244353n,k=map(int,input().split())C=list(map(int,input().split()))D=list(map(int,input().split()))dic=defaultdict(int)dic[(0,0)]=1dp=[-1]*(k+1)dp[0]=0for i in range(k):if dp[i]==-1:continuefor j in range(n):if i+C[j]<=k:if dp[i+C[j]]<=dp[i]+D[j]:dp[i+C[j]]=dp[i]+D[j]dic[(i+C[j],dp[i]+D[j])] += dic[ (i,dp[i]) ]dic[(i+C[j],dp[i]+D[j])]%=modmaxC=max(dp)ans=0for i in range(k+1):if dp[i]==maxC:ans+=dic[(i,maxC)]ans%=modprint(maxC)print(ans)