Submission #1300495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300495		javahirbek	Knapsack (NOI18_knapsack)	Pypy 3	100 / 100	427 ms	87096 KiB

knapsack

import sys
input = sys.stdin.readline

S, N = map(int, input().split())

by_weight = {}

for _ in range(N):
    v, w, k = map(int, input().split())
    if w <= S and k > 0:
        if w not in by_weight:
            by_weight[w] = []
        by_weight[w].append((v, k))

weights_sorted = sorted(by_weight.keys())

best = [[-10**18] * (S + 1) for _ in range(len(weights_sorted) + 1)]
best[0][0] = 0

idx = 1
for w in weights_sorted:
    items = by_weight[w]      
    items.sort(reverse=True)

    for curW in range(0, S + 1):
        best[idx][curW] = best[idx - 1][curW]

        copies = 0
        type_idx = 0
        used = 0
        profit = 0

        while (copies + 1) * w <= curW and type_idx < len(items):
            copies += 1
            profit += items[type_idx][0]

            prev = best[idx - 1][curW - copies * w]
            if prev > -10**18:
                best[idx][curW] = max(best[idx][curW], prev + profit)

            used += 1
            if used == items[type_idx][1]:
                used = 0
                type_idx += 1

    idx += 1

print(max(best[len(weights_sorted)]))

Compilation message (stdout)

Compiling 'knapsack.py'...

=======
  adding: __main__.pyc (deflated 33%)

=======

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