Submission #469826

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
469826	2021-09-02T02:50:59 Z	ImaginaryIQ	Knapsack (NOI18_knapsack)	Java 11	100 / 100	979 ms	59012 KB

knapsack

import java.io.*;
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++) {
			StringTokenizer item = new StringTokenizer(read.readLine());
			int value = Integer.parseInt(item.nextToken());
			int weight = Integer.parseInt(item.nextToken());
			int amt = Integer.parseInt(item.nextToken());
			if (weight <= limit && amt > 0) {
				if (!byWeight.containsKey(weight)) {
					byWeight.put(weight, new ArrayList<>());
				}
				byWeight.get(weight).add(new int[] {value, amt});
			}
		}
 
		/*
		 * best[i][j] contains the most value we can
		 * get using j weight and the first i weight types
		 */
		long[][] best = new long[byWeight.size() + 1][limit + 1];
 
		best[0][0] = 0;
		int at = 1;
		for (var pair : byWeight.entrySet()) {
			int w = pair.getKey();
			ArrayList<int[]> items = pair.getValue();
			// sort items in reverse order by value
			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 currUsed = 0;
				long profit = 0;
				// go through as many items until we run out of items or usable weight
				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
						);
					}
					currUsed++;
					if (currUsed == items.get(typeAt)[1]) {
						currUsed = 0;
						typeAt++;
					}
				}
			}
			at++;
		}
 
		long mostValue = 0;
		for (int i = 0; i <= limit; i++) {
			mostValue = Math.max(mostValue, best[byWeight.size()][i]);
		}
		System.out.println(mostValue);
	}
}

Subtask #1

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	99 ms	8968 KB	Output is correct
2	Correct	85 ms	9072 KB	Output is correct
3	Correct	129 ms	10576 KB	Output is correct
4	Correct	88 ms	9076 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	95 ms	9036 KB	Output is correct
2	Correct	124 ms	10592 KB	Output is correct
3	Correct	127 ms	10548 KB	Output is correct
4	Correct	93 ms	9292 KB	Output is correct
5	Correct	90 ms	8992 KB	Output is correct
6	Correct	134 ms	14420 KB	Output is correct
7	Correct	143 ms	14512 KB	Output is correct
8	Correct	137 ms	14668 KB	Output is correct
9	Correct	139 ms	14668 KB	Output is correct
10	Correct	136 ms	14692 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	95 ms	9036 KB	Output is correct
2	Correct	124 ms	10592 KB	Output is correct
3	Correct	127 ms	10548 KB	Output is correct
4	Correct	93 ms	9292 KB	Output is correct
5	Correct	90 ms	8992 KB	Output is correct
6	Correct	134 ms	14420 KB	Output is correct
7	Correct	143 ms	14512 KB	Output is correct
8	Correct	137 ms	14668 KB	Output is correct
9	Correct	139 ms	14668 KB	Output is correct
10	Correct	136 ms	14692 KB	Output is correct
11	Correct	107 ms	8808 KB	Output is correct
12	Correct	152 ms	10940 KB	Output is correct
13	Correct	125 ms	10536 KB	Output is correct
14	Correct	94 ms	9172 KB	Output is correct
15	Correct	98 ms	9068 KB	Output is correct
16	Correct	157 ms	14952 KB	Output is correct
17	Correct	139 ms	14704 KB	Output is correct
18	Correct	157 ms	14824 KB	Output is correct
19	Correct	171 ms	15052 KB	Output is correct
20	Correct	167 ms	15076 KB	Output is correct

Subtask #4

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	99 ms	8968 KB	Output is correct
2	Correct	85 ms	9072 KB	Output is correct
3	Correct	129 ms	10576 KB	Output is correct
4	Correct	88 ms	9076 KB	Output is correct
5	Correct	95 ms	9036 KB	Output is correct
6	Correct	124 ms	10592 KB	Output is correct
7	Correct	127 ms	10548 KB	Output is correct
8	Correct	93 ms	9292 KB	Output is correct
9	Correct	90 ms	8992 KB	Output is correct
10	Correct	134 ms	14420 KB	Output is correct
11	Correct	143 ms	14512 KB	Output is correct
12	Correct	137 ms	14668 KB	Output is correct
13	Correct	139 ms	14668 KB	Output is correct
14	Correct	136 ms	14692 KB	Output is correct
15	Correct	107 ms	8808 KB	Output is correct
16	Correct	152 ms	10940 KB	Output is correct
17	Correct	125 ms	10536 KB	Output is correct
18	Correct	94 ms	9172 KB	Output is correct
19	Correct	98 ms	9068 KB	Output is correct
20	Correct	157 ms	14952 KB	Output is correct
21	Correct	139 ms	14704 KB	Output is correct
22	Correct	157 ms	14824 KB	Output is correct
23	Correct	171 ms	15052 KB	Output is correct
24	Correct	167 ms	15076 KB	Output is correct
25	Correct	90 ms	9064 KB	Output is correct
26	Correct	135 ms	10728 KB	Output is correct
27	Correct	130 ms	10728 KB	Output is correct
28	Correct	92 ms	9036 KB	Output is correct
29	Correct	96 ms	9136 KB	Output is correct
30	Correct	146 ms	14688 KB	Output is correct
31	Correct	144 ms	14688 KB	Output is correct
32	Correct	156 ms	14736 KB	Output is correct
33	Correct	164 ms	15176 KB	Output is correct
34	Correct	171 ms	15296 KB	Output is correct

Subtask #5

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	99 ms	8968 KB	Output is correct
2	Correct	85 ms	9072 KB	Output is correct
3	Correct	129 ms	10576 KB	Output is correct
4	Correct	88 ms	9076 KB	Output is correct
5	Correct	95 ms	9036 KB	Output is correct
6	Correct	124 ms	10592 KB	Output is correct
7	Correct	127 ms	10548 KB	Output is correct
8	Correct	93 ms	9292 KB	Output is correct
9	Correct	90 ms	8992 KB	Output is correct
10	Correct	134 ms	14420 KB	Output is correct
11	Correct	143 ms	14512 KB	Output is correct
12	Correct	137 ms	14668 KB	Output is correct
13	Correct	139 ms	14668 KB	Output is correct
14	Correct	136 ms	14692 KB	Output is correct
15	Correct	107 ms	8808 KB	Output is correct
16	Correct	152 ms	10940 KB	Output is correct
17	Correct	125 ms	10536 KB	Output is correct
18	Correct	94 ms	9172 KB	Output is correct
19	Correct	98 ms	9068 KB	Output is correct
20	Correct	157 ms	14952 KB	Output is correct
21	Correct	139 ms	14704 KB	Output is correct
22	Correct	157 ms	14824 KB	Output is correct
23	Correct	171 ms	15052 KB	Output is correct
24	Correct	167 ms	15076 KB	Output is correct
25	Correct	90 ms	9064 KB	Output is correct
26	Correct	135 ms	10728 KB	Output is correct
27	Correct	130 ms	10728 KB	Output is correct
28	Correct	92 ms	9036 KB	Output is correct
29	Correct	96 ms	9136 KB	Output is correct
30	Correct	146 ms	14688 KB	Output is correct
31	Correct	144 ms	14688 KB	Output is correct
32	Correct	156 ms	14736 KB	Output is correct
33	Correct	164 ms	15176 KB	Output is correct
34	Correct	171 ms	15296 KB	Output is correct
35	Correct	634 ms	20064 KB	Output is correct
36	Correct	723 ms	20092 KB	Output is correct
37	Correct	668 ms	20292 KB	Output is correct
38	Correct	758 ms	20396 KB	Output is correct
39	Correct	663 ms	20368 KB	Output is correct
40	Correct	770 ms	52400 KB	Output is correct
41	Correct	838 ms	58876 KB	Output is correct
42	Correct	892 ms	58872 KB	Output is correct
43	Correct	937 ms	58932 KB	Output is correct
44	Correct	979 ms	59012 KB	Output is correct
45	Correct	758 ms	24420 KB	Output is correct
46	Correct	456 ms	19816 KB	Output is correct
47	Correct	874 ms	25992 KB	Output is correct
48	Correct	973 ms	37280 KB	Output is correct
49	Correct	562 ms	21392 KB	Output is correct
50	Correct	626 ms	21196 KB	Output is correct