結果

問題 No.2429 Happiest Tabehodai Ways
ユーザー lam6er
提出日時 2025-03-20 21:06:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 60 ms / 2,000 ms
コード長 776 bytes
コンパイル時間 147 ms
コンパイル使用メモリ 82,492 KB
実行使用メモリ 64,684 KB
最終ジャッジ日時 2025-03-20 21:06:25
合計ジャッジ時間 3,147 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff #

MOD = 998244353

N, K = map(int, input().split())
C = list(map(int, input().split()))
D = list(map(int, input().split()))

max_d = [-1] * (K + 1)
count = [0] * (K + 1)

max_d[0] = 0
count[0] = 1

for s in range(K + 1):
    if count[s] == 0:
        continue
    for i in range(N):
        c = C[i]
        d = D[i]
        new_s = s + c
        if new_s > K:
            continue
        new_d = max_d[s] + d
        if new_d > max_d[new_s]:
            max_d[new_s] = new_d
            count[new_s] = count[s]
        elif new_d == max_d[new_s]:
            count[new_s] = (count[new_s] + count[s]) % MOD

max_happiness = max(max_d)
total = 0
for s in range(K + 1):
    if max_d[s] == max_happiness:
        total = (total + count[s]) % MOD

print(max_happiness)
print(total)
0