Submission #1222335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222335		marcusufabc	Knapsack (NOI18_knapsack)	Pypy 3	37 / 100	1094 ms	51112 KiB

knapsack

max_weight, num_items = map(int, input().split())

weights = []
values = []
available_quantity = []

for _ in range(num_items):
    value, weight, qnt = map(int, input().split())
    weights.append(weight)
    values.append(value)
    available_quantity.append(qnt)

# d[i] is the maximum value we can achieve with a basket of weight i
dp = [0] * (max_weight + 1)

# iterate through items
for i in range(num_items):
    weight = weights[i]
    value = values[i]
    quantity = available_quantity[i]

    # process each item for each available unit of it
    for q in range(1, quantity + 1):
        for w in range(max_weight, weight - 1, -1):
            dp[w] = max(dp[w], dp[w - weight] + value)

print(dp[max_weight])

Compilation message (stdout)

Compiling 'knapsack.py'...

=======
  adding: __main__.pyc (deflated 28%)

=======

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