Submission #1148092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148092		aditya_k47	Knapsack (NOI18_knapsack)	Pypy 3	100 / 100	927 ms	129888 KiB

knapsack

# s,n=map(int,input().split())

# v,w,k=[0]*n,[0]*n,[0]*n

# for i in range(n):

#     v[i],w[i],k[i]=map(int,input().split())

# dp=[-float("inf")]*(s+1)
# dp[0]=0

# for i in range(n):

import sys

def knapsack(limit, type_num, items):
    by_weight = {}
    for value, weight, amt in items:
        if weight <= limit and amt > 0:
            if weight not in by_weight:
                by_weight[weight] = []
            by_weight[weight].append((value, amt))
    
    best = [[-float('inf')] * (limit + 1) for _ in range(len(by_weight) + 1)]
    best[0][0] = 0
    
    at = 1
    for w, item_list in sorted(by_weight.items()):
        item_list.sort(reverse=True, key=lambda x: x[0])  # Sort items by value in descending order
        
        for i in range(limit + 1):
            best[at][i] = best[at - 1][i]
            copies, type_at, curr_used, profit = 0, 0, 0, 0
            
            while (copies + 1) * w <= i and type_at < len(item_list):
                copies += 1
                profit += item_list[type_at][0]
                
                if best[at - 1][i - copies * w] != -float('inf'):
                    best[at][i] = max(best[at][i], best[at - 1][i - copies * w] + profit)
                
                curr_used += 1
                if curr_used == item_list[type_at][1]:
                    curr_used = 0
                    type_at += 1
        
        at += 1
    
    return max(best[-1])

if __name__ == "__main__":
    limit, type_num = map(int, sys.stdin.readline().split())
    items = [tuple(map(int, sys.stdin.readline().split())) for _ in range(type_num)]
    print(knapsack(limit, type_num, items))

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: 24 / 24
• Subtask 5: 27 / 27