import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class knapsack {
public static void main(String[] args) throws IOException {
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer initial = new StringTokenizer(read.readLine());
int limit = Integer.parseInt(initial.nextToken());
int typeNum = Integer.parseInt(initial.nextToken());
HashMap<Integer, ArrayList<int[]>> byWeight = new HashMap<>();
for (int t = 0; t < typeNum; t++) {
// value, weight, and amt respectively
int[] item = Arrays.stream(read.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
if (item[1] <= limit && 0 <= item[2]) {
if (!byWeight.containsKey(item[1])) {
byWeight.put(item[1], new ArrayList<>());
}
byWeight.get(item[1]).add(new int[] {item[0], item[2]});
}
}
long[][] best = new long[byWeight.size() + 1][limit + 1];
for (long[] row : best) {
Arrays.fill(row, Integer.MIN_VALUE);
}
best[0][0] = 0;
int at = 1;
for (var pair : byWeight.entrySet()) {
int w = pair.getKey();
ArrayList<int[]> items = pair.getValue();
items.sort(Comparator.comparingInt(i -> -i[0]));
for (int i = 0; i <= limit; i++) {
best[at][i] = best[at - 1][i];
int copies = 0;
int typeAt = 0;
int curr_used = 0;
long profit = 0;
while ((copies + 1) * w <= i && typeAt < items.size()) {
copies++;
profit += items.get(typeAt)[0];
if (best[at - 1][i - copies * w] != Integer.MIN_VALUE) {
best[at][i] = Math.max(
best[at][i],
best[at - 1][i - copies * w] + profit
);
}
curr_used++;
if (curr_used == items.get(typeAt)[1]) {
curr_used = 0;
typeAt++;
}
}
}
at++;
}
System.out.println(Arrays.stream(best[byWeight.size()]).max().getAsLong());
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
103 ms |
9892 KB |
Output is correct |
2 |
Correct |
91 ms |
9112 KB |
Output is correct |
3 |
Correct |
117 ms |
10780 KB |
Output is correct |
4 |
Correct |
112 ms |
9340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
103 ms |
9644 KB |
Output is correct |
2 |
Correct |
125 ms |
10744 KB |
Output is correct |
3 |
Correct |
139 ms |
11024 KB |
Output is correct |
4 |
Correct |
119 ms |
9576 KB |
Output is correct |
5 |
Correct |
100 ms |
9488 KB |
Output is correct |
6 |
Correct |
140 ms |
14520 KB |
Output is correct |
7 |
Correct |
142 ms |
14504 KB |
Output is correct |
8 |
Correct |
140 ms |
14456 KB |
Output is correct |
9 |
Correct |
161 ms |
14620 KB |
Output is correct |
10 |
Correct |
152 ms |
14384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
103 ms |
9644 KB |
Output is correct |
2 |
Correct |
125 ms |
10744 KB |
Output is correct |
3 |
Correct |
139 ms |
11024 KB |
Output is correct |
4 |
Correct |
119 ms |
9576 KB |
Output is correct |
5 |
Correct |
100 ms |
9488 KB |
Output is correct |
6 |
Correct |
140 ms |
14520 KB |
Output is correct |
7 |
Correct |
142 ms |
14504 KB |
Output is correct |
8 |
Correct |
140 ms |
14456 KB |
Output is correct |
9 |
Correct |
161 ms |
14620 KB |
Output is correct |
10 |
Correct |
152 ms |
14384 KB |
Output is correct |
11 |
Correct |
109 ms |
9464 KB |
Output is correct |
12 |
Correct |
161 ms |
11968 KB |
Output is correct |
13 |
Correct |
126 ms |
10764 KB |
Output is correct |
14 |
Correct |
119 ms |
9612 KB |
Output is correct |
15 |
Correct |
103 ms |
9504 KB |
Output is correct |
16 |
Correct |
150 ms |
14732 KB |
Output is correct |
17 |
Correct |
141 ms |
14616 KB |
Output is correct |
18 |
Correct |
150 ms |
14408 KB |
Output is correct |
19 |
Correct |
168 ms |
14600 KB |
Output is correct |
20 |
Correct |
150 ms |
14816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
103 ms |
9892 KB |
Output is correct |
2 |
Correct |
91 ms |
9112 KB |
Output is correct |
3 |
Correct |
117 ms |
10780 KB |
Output is correct |
4 |
Correct |
112 ms |
9340 KB |
Output is correct |
5 |
Correct |
103 ms |
9644 KB |
Output is correct |
6 |
Correct |
125 ms |
10744 KB |
Output is correct |
7 |
Correct |
139 ms |
11024 KB |
Output is correct |
8 |
Correct |
119 ms |
9576 KB |
Output is correct |
9 |
Correct |
100 ms |
9488 KB |
Output is correct |
10 |
Correct |
140 ms |
14520 KB |
Output is correct |
11 |
Correct |
142 ms |
14504 KB |
Output is correct |
12 |
Correct |
140 ms |
14456 KB |
Output is correct |
13 |
Correct |
161 ms |
14620 KB |
Output is correct |
14 |
Correct |
152 ms |
14384 KB |
Output is correct |
15 |
Correct |
109 ms |
9464 KB |
Output is correct |
16 |
Correct |
161 ms |
11968 KB |
Output is correct |
17 |
Correct |
126 ms |
10764 KB |
Output is correct |
18 |
Correct |
119 ms |
9612 KB |
Output is correct |
19 |
Correct |
103 ms |
9504 KB |
Output is correct |
20 |
Correct |
150 ms |
14732 KB |
Output is correct |
21 |
Correct |
141 ms |
14616 KB |
Output is correct |
22 |
Correct |
150 ms |
14408 KB |
Output is correct |
23 |
Correct |
168 ms |
14600 KB |
Output is correct |
24 |
Correct |
150 ms |
14816 KB |
Output is correct |
25 |
Correct |
96 ms |
9472 KB |
Output is correct |
26 |
Correct |
153 ms |
11164 KB |
Output is correct |
27 |
Correct |
127 ms |
10872 KB |
Output is correct |
28 |
Correct |
104 ms |
9836 KB |
Output is correct |
29 |
Correct |
107 ms |
9672 KB |
Output is correct |
30 |
Correct |
159 ms |
14540 KB |
Output is correct |
31 |
Correct |
147 ms |
14504 KB |
Output is correct |
32 |
Correct |
141 ms |
14656 KB |
Output is correct |
33 |
Correct |
145 ms |
14600 KB |
Output is correct |
34 |
Correct |
151 ms |
14460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
103 ms |
9892 KB |
Output is correct |
2 |
Correct |
91 ms |
9112 KB |
Output is correct |
3 |
Correct |
117 ms |
10780 KB |
Output is correct |
4 |
Correct |
112 ms |
9340 KB |
Output is correct |
5 |
Correct |
103 ms |
9644 KB |
Output is correct |
6 |
Correct |
125 ms |
10744 KB |
Output is correct |
7 |
Correct |
139 ms |
11024 KB |
Output is correct |
8 |
Correct |
119 ms |
9576 KB |
Output is correct |
9 |
Correct |
100 ms |
9488 KB |
Output is correct |
10 |
Correct |
140 ms |
14520 KB |
Output is correct |
11 |
Correct |
142 ms |
14504 KB |
Output is correct |
12 |
Correct |
140 ms |
14456 KB |
Output is correct |
13 |
Correct |
161 ms |
14620 KB |
Output is correct |
14 |
Correct |
152 ms |
14384 KB |
Output is correct |
15 |
Correct |
109 ms |
9464 KB |
Output is correct |
16 |
Correct |
161 ms |
11968 KB |
Output is correct |
17 |
Correct |
126 ms |
10764 KB |
Output is correct |
18 |
Correct |
119 ms |
9612 KB |
Output is correct |
19 |
Correct |
103 ms |
9504 KB |
Output is correct |
20 |
Correct |
150 ms |
14732 KB |
Output is correct |
21 |
Correct |
141 ms |
14616 KB |
Output is correct |
22 |
Correct |
150 ms |
14408 KB |
Output is correct |
23 |
Correct |
168 ms |
14600 KB |
Output is correct |
24 |
Correct |
150 ms |
14816 KB |
Output is correct |
25 |
Correct |
96 ms |
9472 KB |
Output is correct |
26 |
Correct |
153 ms |
11164 KB |
Output is correct |
27 |
Correct |
127 ms |
10872 KB |
Output is correct |
28 |
Correct |
104 ms |
9836 KB |
Output is correct |
29 |
Correct |
107 ms |
9672 KB |
Output is correct |
30 |
Correct |
159 ms |
14540 KB |
Output is correct |
31 |
Correct |
147 ms |
14504 KB |
Output is correct |
32 |
Correct |
141 ms |
14656 KB |
Output is correct |
33 |
Correct |
145 ms |
14600 KB |
Output is correct |
34 |
Correct |
151 ms |
14460 KB |
Output is correct |
35 |
Correct |
973 ms |
20276 KB |
Output is correct |
36 |
Execution timed out |
1033 ms |
20696 KB |
Time limit exceeded |
37 |
Halted |
0 ms |
0 KB |
- |