Submission #746237

#	Time	Username	Problem	Language	Result	Execution time	Memory
746237		iamjiamingliu	Knapsack (NOI18_knapsack)	Cpython 3	29 / 100	1073 ms	10580 KiB

knapsack

max_capacity, items_cnt = map(int, input().split())
dp = [[0] * (max_capacity + 1) for _ in range(items_cnt + 1)]

for item_i in range(items_cnt):
    value, weight, quantity = map(int, input().split())
    for cur_capacity in range(max_capacity + 1):
        dp[item_i + 1][cur_capacity] = dp[item_i][cur_capacity]
        if cur_capacity > 0:
            dp[item_i + 1][cur_capacity] = max(dp[item_i + 1][cur_capacity], dp[item_i][cur_capacity - 1])
        for cur_quantity in range(1, quantity + 1):
            if cur_quantity * weight > cur_capacity:
                break
            dp[item_i + 1][cur_capacity] = max(dp[item_i + 1][cur_capacity], dp[item_i][cur_capacity - cur_quantity * weight] + cur_quantity * value)

print(dp[-1][-1])
# print(*dp, sep='\n')

"""
15 5
4 12 1
2 1 1
10 4 1
1 1 1
2 2 1
"""

"""
20 3
5000 15 1
100 1 3
50 1 4
"""

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