結果

問題 No.2866 yuusaan's Knapsack
ユーザー anonymously
提出日時 2024-08-30 23:03:38
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,009 bytes
コンパイル時間 90 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 12,544 KB
最終ジャッジ日時 2024-08-30 23:03:49
合計ジャッジ時間 10,857 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 WA * 9
権限があれば一括ダウンロードができます

ソースコード

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