Submission #1300278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300278		javahirbek	Knapsack (NOI18_knapsack)	Pypy 3	73 / 100	1100 ms	116440 KiB

knapsack

import sys
input = sys.stdin.readline

S, N = map(int, input().split())
Weights = [0]*N
Values = [0]*N
Cnt = [0]*N

for i in range(N):
    Values[i], Weights[i], Cnt[i] = map(int, input().split())

items = []
for i in range(N):
    w = Weights[i]
    v = Values[i]
    c = Cnt[i]
    k = 1
    while c > 0:
        take = min(k, c)
        items.append((w * take, v * take))
        c -= take
        k *= 2

dp = [0] * (S+1)

for w, v in items:
    for j in range(S, w-1, -1):
        dp[j] = max(dp[j], dp[j-w] + v)

print(dp[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