def knapsack():
# Read input
limit, type_num = map(int, input().split())
# Create a list to store items grouped by their weights
by_weight = []
# Populate the list with items
for _ in range(type_num):
value, weight, amount = map(int, input().split())
if weight <= limit and amount > 0:
by_weight.append((weight, value, amount))
# Sort items in ascending order by weight
by_weight.sort()
# Initialize a 2D list to store the best values for different weights and item types
best = [[0] * (limit + 1) for _ in range(len(by_weight) + 1)]
# Iterate through each item type
for i, (w, v, a) in enumerate(by_weight, start=1):
for j in range(limit + 1):
best[i][j] = best[i - 1][j]
for k in range(1, a + 1):
if k * w <= j:
best[i][j] = max(best[i][j], best[i - 1][j - k * w] + k * v)
# Find the maximum value achievable and print it
most_value = max(best[len(by_weight)][i] for i in range(limit + 1))
print(most_value)
if __name__ == "__main__":
knapsack()
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1020 ms |
18992 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
18228 KB |
Output is correct |
2 |
Correct |
43 ms |
21548 KB |
Output is correct |
3 |
Correct |
41 ms |
21264 KB |
Output is correct |
4 |
Correct |
40 ms |
21040 KB |
Output is correct |
5 |
Correct |
39 ms |
21332 KB |
Output is correct |
6 |
Correct |
46 ms |
21296 KB |
Output is correct |
7 |
Correct |
46 ms |
21548 KB |
Output is correct |
8 |
Correct |
46 ms |
21196 KB |
Output is correct |
9 |
Correct |
46 ms |
21296 KB |
Output is correct |
10 |
Correct |
46 ms |
21464 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
18228 KB |
Output is correct |
2 |
Correct |
43 ms |
21548 KB |
Output is correct |
3 |
Correct |
41 ms |
21264 KB |
Output is correct |
4 |
Correct |
40 ms |
21040 KB |
Output is correct |
5 |
Correct |
39 ms |
21332 KB |
Output is correct |
6 |
Correct |
46 ms |
21296 KB |
Output is correct |
7 |
Correct |
46 ms |
21548 KB |
Output is correct |
8 |
Correct |
46 ms |
21196 KB |
Output is correct |
9 |
Correct |
46 ms |
21296 KB |
Output is correct |
10 |
Correct |
46 ms |
21464 KB |
Output is correct |
11 |
Correct |
29 ms |
18228 KB |
Output is correct |
12 |
Correct |
66 ms |
21552 KB |
Output is correct |
13 |
Correct |
41 ms |
21232 KB |
Output is correct |
14 |
Correct |
40 ms |
21036 KB |
Output is correct |
15 |
Correct |
43 ms |
20784 KB |
Output is correct |
16 |
Correct |
57 ms |
21576 KB |
Output is correct |
17 |
Correct |
47 ms |
21500 KB |
Output is correct |
18 |
Correct |
50 ms |
21808 KB |
Output is correct |
19 |
Correct |
52 ms |
21808 KB |
Output is correct |
20 |
Correct |
56 ms |
21732 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1020 ms |
18992 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1020 ms |
18992 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |