結果
問題 | No.2429 Happiest Tabehodai Ways |
ユーザー |
|
提出日時 | 2023-08-24 20:38:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 116 ms / 2,000 ms |
コード長 | 932 bytes |
コンパイル時間 | 428 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 89,984 KB |
最終ジャッジ日時 | 2024-06-12 08:05:32 |
合計ジャッジ時間 | 4,324 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 44 |
ソースコード
from collections import *from itertools import *from functools import *from heapq import *import sys,mathinput = sys.stdin.readlineN,K = map(int,input().split())C = list(map(int,input().split()))D = list(map(int,input().split()))mod = 998244353dp = [-1]*(K+2)dp[0] = 0for i in range(N):c,d = C[i],D[i]for j in range(K):if dp[j]!=-1:dp[min(K+1,j+c)] = max(dp[min(K+1,j+c)],dp[j]+d)e = [[] for _ in range(K+2)]for i in range(N):c,d = C[i],D[i]for j in range(K):k = min(K+1,j+c)if dp[k]-dp[j]==d:e[j].append(k)val = [0]*(K+2)# print(dp)val[0] = 1for i in range(K):for j in e[i]:val[j] += val[i]val[j] %= modM = max(dp[:K+1])ans = 0for j in range(K+1):if dp[j]==M:ans += val[j]ans %= modprint(M)print(ans)