Submission #1300263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300263		javahirbek	Knapsack (NOI18_knapsack)	Pypy 3	0 / 100	172 ms	51076 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())

dp = [[-float('inf')]*(S+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(1, N+1):
    w = Weights[i-1]
    v = Values[i-1]
    c = Cnt[i-1]
    for j in range(S+1):
        Weights[i][j] = Weights[i-1][j]

    for j in range(S, w-1, -1):
        for k in range( c+1):     
            if j - k*w < 0:
                break
            dp[i][j] = max(dp[i][j], dp[i-1][j - k*w] + k*v)

print(dp[N][S])

Compilation message (stdout)

Compiling 'knapsack.py'...

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

=======

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