Submission #746241

#	Time	Username	Problem	Language	Result	Execution time	Memory
746241		iamjiamingliu	Knapsack (NOI18_knapsack)	Cpython 3	29 / 100	1081 ms	2996 KiB

knapsack

max_capacity, items_cnt = map(int, input().split())
prev_state = [0] * (max_capacity + 1)
# 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())
    new_state = prev_state.copy()
    for cur_capacity in range(max_capacity + 1):
        # dp[item_i + 1][cur_capacity] = dp[item_i][cur_capacity]
        if cur_capacity > 0:
            new_state[cur_capacity] = max(new_state[cur_capacity], new_state[cur_capacity - 1])
            # 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
            new_state[cur_capacity] = max(new_state[cur_capacity], prev_state[cur_capacity - cur_quantity * weight] + cur_quantity * value)
            # dp[item_i + 1][cur_capacity] = max(dp[item_i + 1][cur_capacity], dp[item_i][cur_capacity - cur_quantity * weight] + cur_quantity * value)
    prev_state = new_state

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

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