제출 #746242

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
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