結果

問題 No.2866 yuusaan's Knapsack
ユーザー anonymouslyanonymously
提出日時 2024-08-30 23:03:38
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 1,009 bytes
コンパイル時間 90 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 12,544 KB
最終ジャッジ日時 2024-08-30 23:03:49
合計ジャッジ時間 10,857 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 31 ms
10,880 KB
testcase_01 AC 31 ms
11,008 KB
testcase_02 AC 30 ms
10,880 KB
testcase_03 AC 29 ms
10,880 KB
testcase_04 AC 30 ms
11,008 KB
testcase_05 AC 30 ms
10,880 KB
testcase_06 AC 619 ms
12,160 KB
testcase_07 AC 420 ms
12,032 KB
testcase_08 AC 710 ms
12,544 KB
testcase_09 AC 552 ms
12,288 KB
testcase_10 AC 569 ms
11,904 KB
testcase_11 AC 560 ms
12,416 KB
testcase_12 AC 533 ms
12,160 KB
testcase_13 AC 645 ms
12,544 KB
testcase_14 AC 470 ms
12,160 KB
testcase_15 AC 481 ms
11,904 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 274 ms
11,520 KB
testcase_25 WA -
testcase_26 AC 34 ms
10,880 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353
N, W = map(int, input().split())
A = []
V = 0
for i in range(N):
    v, w = map(int, input().split())
    if w < 0:
        V += v
        W -= w
        A.append((-v, -w))
    else:
        A.append((v, w))

maxV = V
dp = [None] * (W + 1)
dp[0] = (V, 1)
for i in range(N):
    for j in range(W, A[i][1] - 1, -1):
        if A[i][0] <= 0:
            continue
        if dp[j - A[i][1]] is not None:
            if dp[j] is None:
                dp[j] = (dp[j - A[i][1]][0] + A[i][0], dp[j - A[i][1]][1])
            elif dp[j - A[i][1]][0] + A[i][0] > dp[j][0]:
                dp[j] = (dp[j - A[i][1]][0] + A[i][0], dp[j - A[i][1]][1])
            elif dp[j - A[i][1]][0] + A[i][0] == dp[j][0]:
                dp[j] = (dp[j][0], (dp[j][1] + dp[j - A[i][1]][1]) % MOD)

ans = 0
for j in range(W + 1):
    if dp[j] is None:
        continue
    if dp[j][0] > maxV:
        maxV = dp[j][0]
        ans = dp[j][1]
    elif dp[j][0] == maxV:
        ans = (ans + dp[j][1]) % MOD
print(maxV, ans)
0