Submission #456391

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
456391	2021-08-06T15:59:21 Z	SansPapyrus683	Knapsack (NOI18_knapsack)	Java 11	73 / 100	1000 ms	58168 KB

knapsack

import java.io.*;
import java.util.*;
 
public final class knapsack {
    private static class Item {
        public int value;
        public int amt;
        public Item(int value, int amt) {
            this.value = value;
            this.amt = amt;
        }
    }
    
    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<Item>> 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 Item(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];
        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<Item> items = pair.getValue();
            // sort items in reverse order by value
            items.sort(Comparator.comparingInt(i -> -i.value));
            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).value;
                    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).amt) {
                        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	95 ms	8884 KB	Output is correct
2	Correct	86 ms	8784 KB	Output is correct
3	Correct	127 ms	10436 KB	Output is correct
4	Correct	97 ms	9008 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	90 ms	9120 KB	Output is correct
2	Correct	115 ms	10452 KB	Output is correct
3	Correct	122 ms	10500 KB	Output is correct
4	Correct	109 ms	9140 KB	Output is correct
5	Correct	110 ms	9020 KB	Output is correct
6	Correct	130 ms	14372 KB	Output is correct
7	Correct	130 ms	14316 KB	Output is correct
8	Correct	135 ms	14444 KB	Output is correct
9	Correct	130 ms	14268 KB	Output is correct
10	Correct	135 ms	14376 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	90 ms	9120 KB	Output is correct
2	Correct	115 ms	10452 KB	Output is correct
3	Correct	122 ms	10500 KB	Output is correct
4	Correct	109 ms	9140 KB	Output is correct
5	Correct	110 ms	9020 KB	Output is correct
6	Correct	130 ms	14372 KB	Output is correct
7	Correct	130 ms	14316 KB	Output is correct
8	Correct	135 ms	14444 KB	Output is correct
9	Correct	130 ms	14268 KB	Output is correct
10	Correct	135 ms	14376 KB	Output is correct
11	Correct	90 ms	8980 KB	Output is correct
12	Correct	148 ms	11140 KB	Output is correct
13	Correct	129 ms	10268 KB	Output is correct
14	Correct	95 ms	9436 KB	Output is correct
15	Correct	91 ms	9056 KB	Output is correct
16	Correct	137 ms	14272 KB	Output is correct
17	Correct	136 ms	14420 KB	Output is correct
18	Correct	134 ms	14372 KB	Output is correct
19	Correct	134 ms	14260 KB	Output is correct
20	Correct	140 ms	14472 KB	Output is correct

Subtask #4

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	95 ms	8884 KB	Output is correct
2	Correct	86 ms	8784 KB	Output is correct
3	Correct	127 ms	10436 KB	Output is correct
4	Correct	97 ms	9008 KB	Output is correct
5	Correct	90 ms	9120 KB	Output is correct
6	Correct	115 ms	10452 KB	Output is correct
7	Correct	122 ms	10500 KB	Output is correct
8	Correct	109 ms	9140 KB	Output is correct
9	Correct	110 ms	9020 KB	Output is correct
10	Correct	130 ms	14372 KB	Output is correct
11	Correct	130 ms	14316 KB	Output is correct
12	Correct	135 ms	14444 KB	Output is correct
13	Correct	130 ms	14268 KB	Output is correct
14	Correct	135 ms	14376 KB	Output is correct
15	Correct	90 ms	8980 KB	Output is correct
16	Correct	148 ms	11140 KB	Output is correct
17	Correct	129 ms	10268 KB	Output is correct
18	Correct	95 ms	9436 KB	Output is correct
19	Correct	91 ms	9056 KB	Output is correct
20	Correct	137 ms	14272 KB	Output is correct
21	Correct	136 ms	14420 KB	Output is correct
22	Correct	134 ms	14372 KB	Output is correct
23	Correct	134 ms	14260 KB	Output is correct
24	Correct	140 ms	14472 KB	Output is correct
25	Correct	90 ms	8968 KB	Output is correct
26	Correct	139 ms	10284 KB	Output is correct
27	Correct	123 ms	10188 KB	Output is correct
28	Correct	117 ms	9200 KB	Output is correct
29	Correct	102 ms	9352 KB	Output is correct
30	Correct	143 ms	14632 KB	Output is correct
31	Correct	142 ms	14432 KB	Output is correct
32	Correct	152 ms	14396 KB	Output is correct
33	Correct	131 ms	14416 KB	Output is correct
34	Correct	135 ms	14532 KB	Output is correct

Subtask #5

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	95 ms	8884 KB	Output is correct
2	Correct	86 ms	8784 KB	Output is correct
3	Correct	127 ms	10436 KB	Output is correct
4	Correct	97 ms	9008 KB	Output is correct
5	Correct	90 ms	9120 KB	Output is correct
6	Correct	115 ms	10452 KB	Output is correct
7	Correct	122 ms	10500 KB	Output is correct
8	Correct	109 ms	9140 KB	Output is correct
9	Correct	110 ms	9020 KB	Output is correct
10	Correct	130 ms	14372 KB	Output is correct
11	Correct	130 ms	14316 KB	Output is correct
12	Correct	135 ms	14444 KB	Output is correct
13	Correct	130 ms	14268 KB	Output is correct
14	Correct	135 ms	14376 KB	Output is correct
15	Correct	90 ms	8980 KB	Output is correct
16	Correct	148 ms	11140 KB	Output is correct
17	Correct	129 ms	10268 KB	Output is correct
18	Correct	95 ms	9436 KB	Output is correct
19	Correct	91 ms	9056 KB	Output is correct
20	Correct	137 ms	14272 KB	Output is correct
21	Correct	136 ms	14420 KB	Output is correct
22	Correct	134 ms	14372 KB	Output is correct
23	Correct	134 ms	14260 KB	Output is correct
24	Correct	140 ms	14472 KB	Output is correct
25	Correct	90 ms	8968 KB	Output is correct
26	Correct	139 ms	10284 KB	Output is correct
27	Correct	123 ms	10188 KB	Output is correct
28	Correct	117 ms	9200 KB	Output is correct
29	Correct	102 ms	9352 KB	Output is correct
30	Correct	143 ms	14632 KB	Output is correct
31	Correct	142 ms	14432 KB	Output is correct
32	Correct	152 ms	14396 KB	Output is correct
33	Correct	131 ms	14416 KB	Output is correct
34	Correct	135 ms	14532 KB	Output is correct
35	Correct	623 ms	19064 KB	Output is correct
36	Correct	716 ms	19132 KB	Output is correct
37	Correct	792 ms	19136 KB	Output is correct
38	Correct	739 ms	19644 KB	Output is correct
39	Correct	659 ms	19592 KB	Output is correct
40	Correct	838 ms	51456 KB	Output is correct
41	Correct	815 ms	57976 KB	Output is correct
42	Correct	853 ms	58100 KB	Output is correct
43	Correct	932 ms	58000 KB	Output is correct
44	Correct	977 ms	58168 KB	Output is correct
45	Correct	715 ms	23892 KB	Output is correct
46	Correct	437 ms	19324 KB	Output is correct
47	Correct	826 ms	25348 KB	Output is correct
48	Execution timed out	1028 ms	36552 KB	Time limit exceeded
49	Halted	0 ms	0 KB	-