Submission #1178547

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178547		GoBananas69	Knapsack (NOI18_knapsack)	Pypy 3	49 / 100	302 ms	327680 KiB

knapsack

import sys
def main() -> None:
    s, n = map(int, input().split())
    if n == 1:
        a, b, c = map(int, input().split())
        x = s // b
        x = min(x, c)
        print(a * x)
        return
    v, w = [], []
    for i in range(n):
        a, b, m = map(int, input().split())
        for j in range(m):
            v.append(a)
            w.append(b)
    n = len(v)
    dp = [[0] * (s + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(s + 1):
            if w[i - 1] > j:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], v[i - 1] + dp[i - 1][j - w[i - 1]])
    print(dp[n][s])


# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')
# sys.stderr = open('output.txt', 'w')
main()

Compilation message (stdout)

Compiling 'knapsack.py'...

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

=======

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