結果

問題 No.2866 yuusaan's Knapsack
ユーザー OhnoHiroki
提出日時 2024-08-30 21:52:57
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 1,058 ms / 2,000 ms
コード長 1,126 bytes
コンパイル時間 95 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 12,672 KB
最終ジャッジ日時 2024-09-26 14:35:36
合計ジャッジ時間 17,954 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

N,W = map(int, input().split())
DP = [(-10**9, 0)] * (2*10**4 + 1)
DP[0] = (0, 1) # value, cnt
P = 998244353

items = [list(map(int, input().split())) for _ in range(N)]
items.sort(key=lambda x:x[1])
for v,w in items:
    if w >= 0:
        for w_ in range(W, -10**4-1, -1):
            if w_ + w <= W:
                v_,c_ = DP[w_]
                if v_+v == DP[w_+w][0]:
                    DP[w_+w] = (v_+v, (DP[w_+w][1]+DP[w_][1]) % P)
                elif v_+v > DP[w_+w][0]:
                    DP[w_+w] = (v_+v, DP[w_][1])
                else:
                    pass
    else:
        for w_ in range(-10**4, 1): #重さが負のものは最初に
            if DP[w_][0] == -10**9:
                continue
            v_,c_ = DP[w_]
            if v_+v == DP[w+w_][0]:
                DP[w_+w] = (v_+v, (DP[w_+w][1]+DP[w_][1]) % P)
            elif v_+v > DP[w+w_][0]:
                DP[w_+w] = (v_+v, DP[w_][1])
            else:
                pass

v_max = -10**9
c_ans = 0
for v,c in DP:
    if v > v_max:
        v_max = v
        c_ans = c
    elif v == v_max:
        c_ans += c

print(v_max, c_ans % P)
0