結果
問題 | No.2429 Happiest Tabehodai Ways |
ユーザー |
|
提出日時 | 2023-08-19 01:24:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 83 ms / 2,000 ms |
コード長 | 695 bytes |
コンパイル時間 | 296 ms |
コンパイル使用メモリ | 81,836 KB |
実行使用メモリ | 66,112 KB |
最終ジャッジ日時 | 2024-06-12 08:02:50 |
合計ジャッジ時間 | 3,644 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 44 |
ソースコード
MOD = 998244353N, K = map(int, input().split())C = list(map(int, input().split()))D = list(map(int, input().split()))CD = []for c, d in zip(C, D):CD.append((c, d))CD.sort()dp = [[-1, -1] for _ in range(K+1)]dp[0] = [0, 1]for k in range(K):if dp[k][0]==-1:continuefor c, d in CD:if c+k>K:breakif dp[c+k][0]<dp[k][0]+d:dp[c+k] = [dp[k][0]+d, dp[k][1]]elif dp[c+k][0]==dp[k][0]+d:dp[c+k][1] += dp[k][1]dp[c+k][1] %= MOD#print(dp)ma = 0ans = 0for d, cnt in dp:if ma<d:ma = dans = cntelif ma==d:ans += cntans %= MODprint(ma)print(ans)