import java.io.*;
import java.util.*;
public class knapsack {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
StringTokenizer st = new StringTokenizer(br.readLine());
int maxWeight = Integer.parseInt(st.nextToken());
int numItemTypes = Integer.parseInt(st.nextToken());
HashMap<Integer, ArrayList<int[]>> weightMap = new HashMap<>();
for (int i = 0; i < numItemTypes; i++) {
st = new StringTokenizer(br.readLine());
int value = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
int copies = Integer.parseInt(st.nextToken());
if (weightMap.containsKey(weight)) {
weightMap.get(weight).add(new int[] {value, copies});
} else {
ArrayList<int[]> itemArray = new ArrayList<>();
itemArray.add(new int[] {value, copies});
weightMap.put(weight, itemArray);
}
}
int[][] maxVal = new int[maxWeight + 1][weightMap.size() + 1];
int currentWeight = 1;
for (var weightCategory : weightMap.entrySet()) {
ArrayList<int[]> weightList = weightCategory.getValue();
int weight = weightCategory.getKey();
int numWeightsConsidered = 0;
for (int[] weightMod : weightList) {
numWeightsConsidered += weightMod[1];
}
numWeightsConsidered = Math.min(numWeightsConsidered, maxWeight/weight);
Collections.sort(weightList, Comparator.comparingInt(j -> -j[0]));
for (int i = 0; i <= maxWeight; i++) {
maxVal[i][currentWeight] = Math.max(maxVal[i][currentWeight], maxVal[i][currentWeight - 1]);
int valAccrued = maxVal[i][currentWeight - 1];
int totalWeight = i;
int weightType = 0;
int j = 0;
// System.out.println(numWeightsConsidered);
while(j < numWeightsConsidered) {
int numCopies = weightList.get(weightType)[1];
while (j < numWeightsConsidered && numCopies > 0) {
// System.out.println(i + "weight " + j + " " + maxVal[i][currentWeight-1] + " " + numCopies + " " + weightList.get(weightType)[0] + " " + weight);
valAccrued += weightList.get(weightType)[0];
totalWeight += weight;
if (totalWeight <= maxWeight)
maxVal[totalWeight][currentWeight] = Math.max(maxVal[totalWeight][currentWeight], valAccrued);
numCopies--;
j++;
}
weightType++;
if (totalWeight > maxWeight)
break;
}
}
currentWeight++;
}
pw.println(maxVal[maxWeight][weightMap.size()]);
br.close();
pw.close();
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
74 ms |
9420 KB |
Output is correct |
2 |
Correct |
69 ms |
9036 KB |
Output is correct |
3 |
Correct |
110 ms |
11428 KB |
Output is correct |
4 |
Correct |
68 ms |
8980 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
71 ms |
9088 KB |
Output is correct |
2 |
Correct |
107 ms |
11004 KB |
Output is correct |
3 |
Correct |
124 ms |
10976 KB |
Output is correct |
4 |
Correct |
81 ms |
9016 KB |
Output is correct |
5 |
Correct |
87 ms |
9300 KB |
Output is correct |
6 |
Correct |
165 ms |
13136 KB |
Output is correct |
7 |
Correct |
143 ms |
13120 KB |
Output is correct |
8 |
Correct |
134 ms |
13300 KB |
Output is correct |
9 |
Correct |
111 ms |
13056 KB |
Output is correct |
10 |
Correct |
164 ms |
13064 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
71 ms |
9088 KB |
Output is correct |
2 |
Correct |
107 ms |
11004 KB |
Output is correct |
3 |
Correct |
124 ms |
10976 KB |
Output is correct |
4 |
Correct |
81 ms |
9016 KB |
Output is correct |
5 |
Correct |
87 ms |
9300 KB |
Output is correct |
6 |
Correct |
165 ms |
13136 KB |
Output is correct |
7 |
Correct |
143 ms |
13120 KB |
Output is correct |
8 |
Correct |
134 ms |
13300 KB |
Output is correct |
9 |
Correct |
111 ms |
13056 KB |
Output is correct |
10 |
Correct |
164 ms |
13064 KB |
Output is correct |
11 |
Correct |
72 ms |
9224 KB |
Output is correct |
12 |
Correct |
148 ms |
12504 KB |
Output is correct |
13 |
Correct |
114 ms |
10860 KB |
Output is correct |
14 |
Correct |
81 ms |
9208 KB |
Output is correct |
15 |
Correct |
85 ms |
9476 KB |
Output is correct |
16 |
Correct |
157 ms |
13444 KB |
Output is correct |
17 |
Correct |
156 ms |
13452 KB |
Output is correct |
18 |
Correct |
143 ms |
13420 KB |
Output is correct |
19 |
Correct |
114 ms |
13072 KB |
Output is correct |
20 |
Correct |
119 ms |
12820 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
74 ms |
9420 KB |
Output is correct |
2 |
Correct |
69 ms |
9036 KB |
Output is correct |
3 |
Correct |
110 ms |
11428 KB |
Output is correct |
4 |
Correct |
68 ms |
8980 KB |
Output is correct |
5 |
Correct |
71 ms |
9088 KB |
Output is correct |
6 |
Correct |
107 ms |
11004 KB |
Output is correct |
7 |
Correct |
124 ms |
10976 KB |
Output is correct |
8 |
Correct |
81 ms |
9016 KB |
Output is correct |
9 |
Correct |
87 ms |
9300 KB |
Output is correct |
10 |
Correct |
165 ms |
13136 KB |
Output is correct |
11 |
Correct |
143 ms |
13120 KB |
Output is correct |
12 |
Correct |
134 ms |
13300 KB |
Output is correct |
13 |
Correct |
111 ms |
13056 KB |
Output is correct |
14 |
Correct |
164 ms |
13064 KB |
Output is correct |
15 |
Correct |
72 ms |
9224 KB |
Output is correct |
16 |
Correct |
148 ms |
12504 KB |
Output is correct |
17 |
Correct |
114 ms |
10860 KB |
Output is correct |
18 |
Correct |
81 ms |
9208 KB |
Output is correct |
19 |
Correct |
85 ms |
9476 KB |
Output is correct |
20 |
Correct |
157 ms |
13444 KB |
Output is correct |
21 |
Correct |
156 ms |
13452 KB |
Output is correct |
22 |
Correct |
143 ms |
13420 KB |
Output is correct |
23 |
Correct |
114 ms |
13072 KB |
Output is correct |
24 |
Correct |
119 ms |
12820 KB |
Output is correct |
25 |
Correct |
72 ms |
9108 KB |
Output is correct |
26 |
Correct |
117 ms |
11624 KB |
Output is correct |
27 |
Correct |
111 ms |
10900 KB |
Output is correct |
28 |
Correct |
86 ms |
9284 KB |
Output is correct |
29 |
Incorrect |
80 ms |
9044 KB |
Output isn't correct |
30 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
74 ms |
9420 KB |
Output is correct |
2 |
Correct |
69 ms |
9036 KB |
Output is correct |
3 |
Correct |
110 ms |
11428 KB |
Output is correct |
4 |
Correct |
68 ms |
8980 KB |
Output is correct |
5 |
Correct |
71 ms |
9088 KB |
Output is correct |
6 |
Correct |
107 ms |
11004 KB |
Output is correct |
7 |
Correct |
124 ms |
10976 KB |
Output is correct |
8 |
Correct |
81 ms |
9016 KB |
Output is correct |
9 |
Correct |
87 ms |
9300 KB |
Output is correct |
10 |
Correct |
165 ms |
13136 KB |
Output is correct |
11 |
Correct |
143 ms |
13120 KB |
Output is correct |
12 |
Correct |
134 ms |
13300 KB |
Output is correct |
13 |
Correct |
111 ms |
13056 KB |
Output is correct |
14 |
Correct |
164 ms |
13064 KB |
Output is correct |
15 |
Correct |
72 ms |
9224 KB |
Output is correct |
16 |
Correct |
148 ms |
12504 KB |
Output is correct |
17 |
Correct |
114 ms |
10860 KB |
Output is correct |
18 |
Correct |
81 ms |
9208 KB |
Output is correct |
19 |
Correct |
85 ms |
9476 KB |
Output is correct |
20 |
Correct |
157 ms |
13444 KB |
Output is correct |
21 |
Correct |
156 ms |
13452 KB |
Output is correct |
22 |
Correct |
143 ms |
13420 KB |
Output is correct |
23 |
Correct |
114 ms |
13072 KB |
Output is correct |
24 |
Correct |
119 ms |
12820 KB |
Output is correct |
25 |
Correct |
72 ms |
9108 KB |
Output is correct |
26 |
Correct |
117 ms |
11624 KB |
Output is correct |
27 |
Correct |
111 ms |
10900 KB |
Output is correct |
28 |
Correct |
86 ms |
9284 KB |
Output is correct |
29 |
Incorrect |
80 ms |
9044 KB |
Output isn't correct |
30 |
Halted |
0 ms |
0 KB |
- |