Submission #746242

#	Time	Username	Problem	Language	Result	Execution time	Memory
746242		iamjiamingliu	Knapsack (NOI18_knapsack)	Pypy 3	73 / 100	1091 ms	24888 KiB

knapsack

max_capacity, items_cnt = map(int, input().split())
prev_state = [0] * (max_capacity + 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):
        if cur_capacity > 0:
            new_state[cur_capacity] = max(new_state[cur_capacity], new_state[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)
    prev_state = new_state

print(prev_state[-1])

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