Submission #1355055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1355055		li1005345206	Knapsack (NOI18_knapsack)	Pypy 3	73 / 100	241 ms	327680 KiB

knapsack

import os
import sys
input=lambda:sys.stdin.readline().strip()
minput=lambda:map(int,input().split())
S,N=minput()
kvw=[minput() for i in range(N)]
kvw2=[]
while kvw:
    V,W,K=kvw.pop()
    base = 1
    while K >= base:
        K -= base
        kvw2.append((V * base, W * base, 1))
        base <<= 1
    if K > 0:
        kvw.append((V * K, W * K, 1))
n = len(kvw2)
dp = [[0] * (S + 1) for _ in range(2)]
for i in range(n):
    V,W,K = kvw2[i]
    ind = (i + 1) & 1 
    prev = i & 1
    for j in range(S + 1):
        dp[ind][j] = dp[prev][j]
        if j >= W:
            dp[ind][j] = max(dp[ind][j], dp[prev][j - W] + V)
print(max(map(max, dp)))

Compilation message (stdout)

Compiling 'knapsack.py'...

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

=======

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