Submission #1357192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1357192		po_rag526	Knapsack (NOI18_knapsack)	Pypy 3	73 / 100	1112 ms	270700 KiB

knapsack

from sys import stdin
data = stdin.buffer.read().split()

s = int(data[0])
n = int(data[1])

items = []
idx = 2
for _ in range(n):
    v = int(data[idx])
    w = int(data[idx + 1])
    k = int(data[idx + 2])
    idx += 3

    qty = 1
    remaining = k
    while qty <= remaining:
        items.append(((v * qty), (w * qty)))
        remaining -= qty
        qty <<= 1
    if remaining:
        items.append(((v * remaining), (w * remaining)))

fml = [0] * (s + 1)
for value, weight in items:
    if weight > s:
        continue
    for cap in range(s, weight - 1, -1):
        yay = fml[cap - weight] + value
        if yay > fml[cap]:
            fml[cap] = yay

print(fml[s])

Compilation message (stdout)

Compiling 'knapsack.py'...

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

=======

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