Submission #954977

#	Time	Username	Problem	Language	Result	Execution time	Memory
954977		vis786	Knapsack (NOI18_knapsack)	Cpython 3	49 / 100	1086 ms	24212 KiB

knapsack

S,N = map(int,input().split())
V,W,K = [],[],[]
for n in range(N):
    Vi,Wi,Ki = map(int,input().split())
    V.append(Vi)
    W.append(Wi)
    K.append(Ki)
mem = {}
def maxValue(weight,i):
    if (weight,i) in mem:
        return mem[(weight,i)]
    if i == N:
        return 0
    m = 0
    count = K[i]
    new_weight = weight
    new_i = i+1
    while count >= 0 and new_weight <= S:
        m = max(m,maxValue(new_weight,new_i)+(K[i]-count)*V[i])
        count -= 1
        new_weight += W[i]
    mem[(weight,i)] = m
    return mem[(weight,i)]
print(maxValue(0,0))

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