Submission #886850

#	Time	Username	Problem	Language	Result	Execution time	Memory
886850		rafc	Knapsack (NOI18_knapsack)	Pypy 3	37 / 100	1020 ms	21808 KiB

knapsack

def knapsack():
    # Read input
    limit, type_num = map(int, input().split())

    # Create a list to store items grouped by their weights
    by_weight = []

    # Populate the list with items
    for _ in range(type_num):
        value, weight, amount = map(int, input().split())
        if weight <= limit and amount > 0:
            by_weight.append((weight, value, amount))

    # Sort items in ascending order by weight
    by_weight.sort()

    # Initialize a 2D list to store the best values for different weights and item types
    best = [[0] * (limit + 1) for _ in range(len(by_weight) + 1)]

    # Iterate through each item type
    for i, (w, v, a) in enumerate(by_weight, start=1):
        for j in range(limit + 1):
            best[i][j] = best[i - 1][j]
            for k in range(1, a + 1):
                if k * w <= j:
                    best[i][j] = max(best[i][j], best[i - 1][j - k * w] + k * v)

    # Find the maximum value achievable and print it
    most_value = max(best[len(by_weight)][i] for i in range(limit + 1))
    print(most_value)

if __name__ == "__main__":
    knapsack()

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