結果

問題 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,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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 89 ms
11,904 KB
testcase_01 AC 51 ms
11,904 KB
testcase_02 AC 71 ms
11,776 KB
testcase_03 AC 37 ms
10,880 KB
testcase_04 AC 42 ms
10,880 KB
testcase_05 AC 43 ms
10,880 KB
testcase_06 AC 791 ms
12,160 KB
testcase_07 AC 589 ms
11,904 KB
testcase_08 AC 874 ms
12,288 KB
testcase_09 AC 799 ms
12,288 KB
testcase_10 AC 626 ms
12,032 KB
testcase_11 AC 619 ms
12,544 KB
testcase_12 AC 786 ms
12,544 KB
testcase_13 AC 748 ms
12,672 KB
testcase_14 AC 643 ms
11,904 KB
testcase_15 AC 688 ms
11,904 KB
testcase_16 AC 565 ms
11,776 KB
testcase_17 AC 1,014 ms
12,416 KB
testcase_18 AC 551 ms
12,544 KB
testcase_19 AC 773 ms
11,776 KB
testcase_20 AC 747 ms
12,416 KB
testcase_21 AC 763 ms
12,160 KB
testcase_22 AC 642 ms
11,904 KB
testcase_23 AC 1,058 ms
12,416 KB
testcase_24 AC 484 ms
11,520 KB
testcase_25 AC 760 ms
12,160 KB
testcase_26 AC 1,034 ms
11,648 KB
testcase_27 AC 61 ms
11,776 KB
testcase_28 AC 767 ms
12,160 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