結果

問題 No.2866 yuusaan's Knapsack
ユーザー OhnoHirokiOhnoHiroki
提出日時 2024-08-30 21:52:57
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 1,046 ms / 2,000 ms
コード長 1,126 bytes
コンパイル時間 92 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 12,800 KB
最終ジャッジ日時 2024-08-31 01:27:45
合計ジャッジ時間 16,556 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 85 ms
12,032 KB
testcase_01 AC 45 ms
12,032 KB
testcase_02 AC 70 ms
11,904 KB
testcase_03 AC 34 ms
11,136 KB
testcase_04 AC 39 ms
11,008 KB
testcase_05 AC 39 ms
11,008 KB
testcase_06 AC 858 ms
12,160 KB
testcase_07 AC 599 ms
12,160 KB
testcase_08 AC 811 ms
12,416 KB
testcase_09 AC 772 ms
12,544 KB
testcase_10 AC 617 ms
12,160 KB
testcase_11 AC 617 ms
12,800 KB
testcase_12 AC 759 ms
12,672 KB
testcase_13 AC 682 ms
12,800 KB
testcase_14 AC 630 ms
12,160 KB
testcase_15 AC 660 ms
12,032 KB
testcase_16 AC 537 ms
11,904 KB
testcase_17 AC 946 ms
12,544 KB
testcase_18 AC 546 ms
12,544 KB
testcase_19 AC 793 ms
11,904 KB
testcase_20 AC 720 ms
12,416 KB
testcase_21 AC 771 ms
12,288 KB
testcase_22 AC 622 ms
12,160 KB
testcase_23 AC 1,046 ms
12,544 KB
testcase_24 AC 483 ms
11,648 KB
testcase_25 AC 737 ms
12,160 KB
testcase_26 AC 989 ms
11,904 KB
testcase_27 AC 57 ms
11,904 KB
権限があれば一括ダウンロードができます

ソースコード

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