제출 #886846

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
886846		rafc	Knapsack (NOI18_knapsack)	Pypy 3	12 / 100	30 ms	18372 KiB

knapsack

import sys

def main():
    read = sys.stdin.readline
    s, n = (int(i) for i in read().split())
    values = []
    weights = []
    quantities = []
    sorted_values = []

    for index in range(n):
        v_i, w_i, k_i = (int(i) for i in read().split())
        values.append(v_i)
        weights.append(w_i)
        quantities.append(k_i)
        sorted_values.append((v_i / w_i, index))

    sorted_values.sort(reverse=True)

    curr_weight = 0
    curr_total = 0
    for i in range(len(sorted_values)):
        _, idx = sorted_values[i]
        value = values[idx]
        weight = weights[idx]
        quantity = quantities[idx]
        remaining_weight = s - curr_weight
        quantity_to_grab = min(remaining_weight // weight, quantity)
        curr_total += quantity_to_grab * value
        curr_weight += quantity_to_grab * weight
    print(curr_total)

if __name__ == '__main__':
    main()

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