Submission #1355377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1355377		li1005345206	Knapsack (NOI18_knapsack)	Pypy 3	73 / 100	1101 ms	198888 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)]
dp = [[0] * (S + 1) for _ in range(2)]
ind = 0
while kvw:
    V,W,K=kvw.pop()
    base = 1
    if K > 2047:
        K = 2047
    while K > 0:
        if K >= base:
            K -= base
        else:
            base = K
            K = 0
        v = V * base
        w = W * base
        prev = ind & 1
        ind = (ind + 1) & 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)
        base <<= 1
print(max(map(max, dp)))

Compilation message (stdout)

Compiling 'knapsack.py'...

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

=======

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