結果
問題 | No.2866 yuusaan's Knapsack |
ユーザー | akasia_midori |
提出日時 | 2024-08-30 23:42:13 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 271 ms / 2,000 ms |
コード長 | 1,635 bytes |
コンパイル時間 | 304 ms |
コンパイル使用メモリ | 82,288 KB |
実行使用メモリ | 130,456 KB |
最終ジャッジ日時 | 2024-09-19 09:04:10 |
合計ジャッジ時間 | 6,172 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 59 ms
67,968 KB |
testcase_01 | AC | 56 ms
66,944 KB |
testcase_02 | AC | 67 ms
72,192 KB |
testcase_03 | AC | 48 ms
62,464 KB |
testcase_04 | AC | 50 ms
62,080 KB |
testcase_05 | AC | 51 ms
62,208 KB |
testcase_06 | AC | 202 ms
112,776 KB |
testcase_07 | AC | 176 ms
98,304 KB |
testcase_08 | AC | 225 ms
114,060 KB |
testcase_09 | AC | 228 ms
115,168 KB |
testcase_10 | AC | 182 ms
98,444 KB |
testcase_11 | AC | 207 ms
108,160 KB |
testcase_12 | AC | 210 ms
109,940 KB |
testcase_13 | AC | 218 ms
110,300 KB |
testcase_14 | AC | 191 ms
101,328 KB |
testcase_15 | AC | 176 ms
100,320 KB |
testcase_16 | AC | 194 ms
99,416 KB |
testcase_17 | AC | 257 ms
123,100 KB |
testcase_18 | AC | 205 ms
105,564 KB |
testcase_19 | AC | 227 ms
110,824 KB |
testcase_20 | AC | 233 ms
116,460 KB |
testcase_21 | AC | 225 ms
112,188 KB |
testcase_22 | AC | 208 ms
109,696 KB |
testcase_23 | AC | 271 ms
130,456 KB |
testcase_24 | AC | 166 ms
95,136 KB |
testcase_25 | AC | 228 ms
112,744 KB |
testcase_26 | AC | 180 ms
104,576 KB |
testcase_27 | AC | 65 ms
69,888 KB |
ソースコード
def oi(): return int(input()) def os(): return input().rstrip() def mi(): return list(map(int, input().split())) # import sys # input = sys.stdin.readline # import sys # sys.setrecursionlimit(10**8) # import pypyjit # pypyjit.set_param('max_unroll_recursion=-1') input_count = 0 N,W = mi() items = [] for _ in range(N): v,w = mi() items.append((w,v)) items.sort() mod = 998244353 mins = 10000 value_dp = [[-1*float("inf")]*(mins +W + 10) for _ in range(N+1)] num_dp = [[-1*float("inf")]*(mins +W + 10) for _ in range(N+1)] for i in range(1, N+1): w,v = items[i-1] if 0 <= w+mins <= W+mins: value_dp[i][w+mins] = v num_dp[i][w+mins] = 1 for j in range(W+1 + mins): # if value_dp[i][j] < value_dp[i-1][j]: num_dp[i][j] = num_dp[i-1][j] elif value_dp[i][j] == value_dp[i-1][j]: num_dp[i][j] = (num_dp[i][j] + num_dp[i-1][j])%mod value_dp[i][j] = max(value_dp[i][j], value_dp[i-1][j]) if 0 <= j+w <= W+mins and value_dp[i-1][j]!=0: if value_dp[i][j+w] < value_dp[i-1][j] + v: value_dp[i][j+w] = value_dp[i-1][j] + v num_dp[i][j+w] = num_dp[i-1][j] elif value_dp[i][j+w] == (value_dp[i-1][j] + v): # value_dp[i][j+w] = max(value_dp[i][j+w], value_dp[i-1][j] + v) num_dp[i][j+w] = (num_dp[i][j+w] + num_dp[i-1][j])%mod sums = 0 maxs_v = max(value_dp[-1][:W+mins + 1]) for i in range(W+mins + 1): if value_dp[-1][i] == maxs_v: sums = (num_dp[-1][i] + sums)%mod if maxs_v < 0: print(*[0,1]) else: print(*[maxs_v, sums])