Submission #1300289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300289		javahirbek	Knapsack (NOI18_knapsack)	Pypy 3	73 / 100	1061 ms	51832 KiB

knapsack

import sys
input = sys.stdin.buffer.readline

S, N = map(int, input().split())
dp = [0] * (S+1)

for _ in range(N):
    v, w, c = map(int, input().split())
    if c * w >= S: 
        for j in range(w, S+1):
            dp[j] = max(dp[j], dp[j-w] + v)
    else:
        for r in range(w):
            q = []
            for k in range((S-r)//w + 1):
                idx = r + k*w
                val = dp[idx] - k*v
                while q and q[-1][1] <= val:
                    q.pop()
                q.append((k, val))
                while q and q[0][0] < k - c:
                    q.pop(0)
                dp[idx] = max(dp[idx], q[0][1] + k*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