Submission #544704

#	Time	Username	Problem	Language	Result	Execution time	Memory
544704		KunalKapoor25	Knapsack (NOI18_knapsack)	Pypy 3	17 / 100	1089 ms	38472 KiB

knapsack

#dp[i][j] --- i represents using the first i items where items w same weight are grouped and j is the total weight
import math

s, n = map(int, input().split())
item_dict = {}
for x in range(n):
    v, w, k = map(int, input().split())
    if w in item_dict:
        for y in range(k):
            item_dict[w].append(v)
    else:
        item_dict[w] = [v for y in range(k)]
for key in item_dict.keys():
    item_dict[key].sort(reverse=True)
items = sorted(item_dict.keys())
dp = [[0 for j in range(s+1)] for i in range(len(items)+1)]

for j in range(s+1):
    for i in range(0, len(items)):
        dp[i+1][j] = dp[i][j]
        for k in range(len(item_dict[items[i]])):
            if j-items[i]*(k+1) >= 0:
                dp[i+1][j] = max(dp[i+1][j], dp[i][j-items[i]*(k+1)] + sum(item_dict[items[i]][:k+1]))
        #dp[i+1][j] = max(dp[i+1][j], sum(item_dict[items[i]][:min(len(item_dict[items[i]]), math.ceil(s/items[i]))]))

print(dp[-1][-1])

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