Submission #8518414

---

Source Code Expand

from collections import defaultdict
from itertools import product, accumulate

N, W = map(int, input().split())
items = defaultdict(list)
for _ in range(N):
    w, v = map(int, input().split())
    items[w].append(v)
weights = list(items.keys())
nums = {w: len(items[w]) for w in weights}
cumsum = {w: None for w in weights}
for i, w in enumerate(weights):
    items[w].sort(reverse=True)
    cumsum[w] = [0] + list(accumulate(items[w]))
ans = 0
for tup in product(*[range(nums[w] + 1) for w in weights]):
    temp_weight = sum(w * t for w, t in zip(weights, tup))
    if temp_weight > W: continue
    temp_value = sum(cumsum[w][t] for w, t in zip(weights, tup))
    ans = max(temp_value, ans)
print(ans)

Submission Info

Judge Result