Submission #868636

#	Time	Username	Problem	Language	Result	Execution time	Memory
868636		iamjiamingliu	Knapsack (NOI18_knapsack)	Pypy 3	73 / 100	1047 ms	115300 KiB

knapsack

import math
from functools import reduce

# Used by bounded knapsack
def zero_one_knapsack(weights, values, weight_limit: int) -> int:
    w_gcd = reduce(math.gcd, [*weights, weight_limit])
    weights = [w // w_gcd for w in weights]
    weight_limit //= w_gcd
    dp = [0] * (weight_limit + 1)
    for item_i in range(len(weights)):
        new_dp = dp.copy()
        for w in range(weights[item_i], weight_limit + 1):
            new_dp[w] = max(dp[w], dp[w - weights[item_i]] + values[item_i])
        dp = new_dp
    return dp[weight_limit]

def bounded_knapsack(weights, values, quantities, weight_limit: int) -> int:
    adjusted_items = []
    for w, v, q in zip(weights, values, quantities):
        chunk = 1
        while chunk <= q:
            adjusted_items.append((w * chunk, v * chunk))
            q -= chunk
            chunk <<= 1
        if q:
            adjusted_items.append((w * q, v * q))
    return zero_one_knapsack([item[0] for item in adjusted_items], [item[1] for item in adjusted_items], weight_limit)


if __name__ == '__main__':
    weight_limit, items_cnt = map(int, input().split())
    items = [list(map(int, input().split())) for _ in range(items_cnt)]
    vs = [i[0] for i in items]
    ws = [i[1] for i in items]
    qs = [i[2] for i in items]
    print(bounded_knapsack(ws, vs, qs, weight_limit))

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27