oj.uz

Submission #544704

# Submission time Handle Problem Language Result Execution time Memory
544704 2022-04-02T15:33:48 Z KunalKapoor25 Knapsack (NOI18_knapsack) PyPy 3
17 / 100
 1000 ms 38472 KB 
#dp[i][j] --- i represents using the first i items where items w same weight are grouped and j is the total weight
import math

s, n = map(int, input().split())
item_dict = {}
for x in range(n):
    v, w, k = map(int, input().split())
    if w in item_dict:
        for y in range(k):
            item_dict[w].append(v)
    else:
        item_dict[w] = [v for y in range(k)]
for key in item_dict.keys():
    item_dict[key].sort(reverse=True)
items = sorted(item_dict.keys())
dp = [[0 for j in range(s+1)] for i in range(len(items)+1)]

for j in range(s+1):
    for i in range(0, len(items)):
        dp[i+1][j] = dp[i][j]
        for k in range(len(item_dict[items[i]])):
            if j-items[i]*(k+1) >= 0:
                dp[i+1][j] = max(dp[i+1][j], dp[i][j-items[i]*(k+1)] + sum(item_dict[items[i]][:k+1]))
        #dp[i+1][j] = max(dp[i+1][j], sum(item_dict[items[i]][:min(len(item_dict[items[i]]), math.ceil(s/items[i]))]))

print(dp[-1][-1])

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 38472 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 18208 KB Output is correct
2 Correct 130 ms 20760 KB Output is correct
3 Correct 98 ms 20672 KB Output is correct
4 Correct 50 ms 19408 KB Output is correct
5 Correct 51 ms 19412 KB Output is correct
6 Correct 102 ms 24056 KB Output is correct
7 Correct 106 ms 24092 KB Output is correct
8 Correct 94 ms 24064 KB Output is correct
9 Correct 88 ms 23592 KB Output is correct
10 Correct 108 ms 24228 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 18208 KB Output is correct
2 Correct 130 ms 20760 KB Output is correct
3 Correct 98 ms 20672 KB Output is correct
4 Correct 50 ms 19408 KB Output is correct
5 Correct 51 ms 19412 KB Output is correct
6 Correct 102 ms 24056 KB Output is correct
7 Correct 106 ms 24092 KB Output is correct
8 Correct 94 ms 24064 KB Output is correct
9 Correct 88 ms 23592 KB Output is correct
10 Correct 108 ms 24228 KB Output is correct
11 Correct 46 ms 18220 KB Output is correct
12 Execution timed out 1089 ms 23152 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 38472 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 38472 KB Time limit exceeded
2 Halted 0 ms 0 KB -