Submission #456388

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
456388	2021-08-06T15:58:22 Z	SansPapyrus683	Knapsack (NOI18_knapsack)	Java 11	73 / 100	1000 ms	58280 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	93 ms	9320 KB	Output is correct
2	Correct	90 ms	8892 KB	Output is correct
3	Correct	118 ms	10360 KB	Output is correct
4	Correct	84 ms	8904 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	88 ms	8996 KB	Output is correct
2	Correct	138 ms	10320 KB	Output is correct
3	Correct	115 ms	10256 KB	Output is correct
4	Correct	102 ms	9268 KB	Output is correct
5	Correct	90 ms	9136 KB	Output is correct
6	Correct	133 ms	14344 KB	Output is correct
7	Correct	131 ms	14312 KB	Output is correct
8	Correct	156 ms	14564 KB	Output is correct
9	Correct	130 ms	14320 KB	Output is correct
10	Correct	129 ms	14580 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	88 ms	8996 KB	Output is correct
2	Correct	138 ms	10320 KB	Output is correct
3	Correct	115 ms	10256 KB	Output is correct
4	Correct	102 ms	9268 KB	Output is correct
5	Correct	90 ms	9136 KB	Output is correct
6	Correct	133 ms	14344 KB	Output is correct
7	Correct	131 ms	14312 KB	Output is correct
8	Correct	156 ms	14564 KB	Output is correct
9	Correct	130 ms	14320 KB	Output is correct
10	Correct	129 ms	14580 KB	Output is correct
11	Correct	93 ms	9024 KB	Output is correct
12	Correct	146 ms	11052 KB	Output is correct
13	Correct	117 ms	10116 KB	Output is correct
14	Correct	114 ms	9252 KB	Output is correct
15	Correct	89 ms	9160 KB	Output is correct
16	Correct	131 ms	14712 KB	Output is correct
17	Correct	132 ms	14264 KB	Output is correct
18	Correct	135 ms	14248 KB	Output is correct
19	Correct	134 ms	14404 KB	Output is correct
20	Correct	135 ms	14404 KB	Output is correct

Subtask #4

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	93 ms	9320 KB	Output is correct
2	Correct	90 ms	8892 KB	Output is correct
3	Correct	118 ms	10360 KB	Output is correct
4	Correct	84 ms	8904 KB	Output is correct
5	Correct	88 ms	8996 KB	Output is correct
6	Correct	138 ms	10320 KB	Output is correct
7	Correct	115 ms	10256 KB	Output is correct
8	Correct	102 ms	9268 KB	Output is correct
9	Correct	90 ms	9136 KB	Output is correct
10	Correct	133 ms	14344 KB	Output is correct
11	Correct	131 ms	14312 KB	Output is correct
12	Correct	156 ms	14564 KB	Output is correct
13	Correct	130 ms	14320 KB	Output is correct
14	Correct	129 ms	14580 KB	Output is correct
15	Correct	93 ms	9024 KB	Output is correct
16	Correct	146 ms	11052 KB	Output is correct
17	Correct	117 ms	10116 KB	Output is correct
18	Correct	114 ms	9252 KB	Output is correct
19	Correct	89 ms	9160 KB	Output is correct
20	Correct	131 ms	14712 KB	Output is correct
21	Correct	132 ms	14264 KB	Output is correct
22	Correct	135 ms	14248 KB	Output is correct
23	Correct	134 ms	14404 KB	Output is correct
24	Correct	135 ms	14404 KB	Output is correct
25	Correct	89 ms	9044 KB	Output is correct
26	Correct	134 ms	10620 KB	Output is correct
27	Correct	119 ms	10376 KB	Output is correct
28	Correct	100 ms	9244 KB	Output is correct
29	Correct	99 ms	9456 KB	Output is correct
30	Correct	148 ms	14332 KB	Output is correct
31	Correct	134 ms	14444 KB	Output is correct
32	Correct	141 ms	14340 KB	Output is correct
33	Correct	134 ms	14452 KB	Output is correct
34	Correct	151 ms	14420 KB	Output is correct

Subtask #5

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	93 ms	9320 KB	Output is correct
2	Correct	90 ms	8892 KB	Output is correct
3	Correct	118 ms	10360 KB	Output is correct
4	Correct	84 ms	8904 KB	Output is correct
5	Correct	88 ms	8996 KB	Output is correct
6	Correct	138 ms	10320 KB	Output is correct
7	Correct	115 ms	10256 KB	Output is correct
8	Correct	102 ms	9268 KB	Output is correct
9	Correct	90 ms	9136 KB	Output is correct
10	Correct	133 ms	14344 KB	Output is correct
11	Correct	131 ms	14312 KB	Output is correct
12	Correct	156 ms	14564 KB	Output is correct
13	Correct	130 ms	14320 KB	Output is correct
14	Correct	129 ms	14580 KB	Output is correct
15	Correct	93 ms	9024 KB	Output is correct
16	Correct	146 ms	11052 KB	Output is correct
17	Correct	117 ms	10116 KB	Output is correct
18	Correct	114 ms	9252 KB	Output is correct
19	Correct	89 ms	9160 KB	Output is correct
20	Correct	131 ms	14712 KB	Output is correct
21	Correct	132 ms	14264 KB	Output is correct
22	Correct	135 ms	14248 KB	Output is correct
23	Correct	134 ms	14404 KB	Output is correct
24	Correct	135 ms	14404 KB	Output is correct
25	Correct	89 ms	9044 KB	Output is correct
26	Correct	134 ms	10620 KB	Output is correct
27	Correct	119 ms	10376 KB	Output is correct
28	Correct	100 ms	9244 KB	Output is correct
29	Correct	99 ms	9456 KB	Output is correct
30	Correct	148 ms	14332 KB	Output is correct
31	Correct	134 ms	14444 KB	Output is correct
32	Correct	141 ms	14340 KB	Output is correct
33	Correct	134 ms	14452 KB	Output is correct
34	Correct	151 ms	14420 KB	Output is correct
35	Correct	633 ms	19320 KB	Output is correct
36	Correct	685 ms	19424 KB	Output is correct
37	Correct	660 ms	19320 KB	Output is correct
38	Correct	772 ms	19672 KB	Output is correct
39	Correct	657 ms	19768 KB	Output is correct
40	Correct	827 ms	51348 KB	Output is correct
41	Correct	814 ms	58164 KB	Output is correct
42	Correct	885 ms	58280 KB	Output is correct
43	Correct	934 ms	58252 KB	Output is correct
44	Correct	992 ms	58208 KB	Output is correct
45	Correct	731 ms	23780 KB	Output is correct
46	Correct	446 ms	19380 KB	Output is correct
47	Correct	872 ms	25160 KB	Output is correct
48	Execution timed out	1026 ms	36464 KB	Time limit exceeded
49	Halted	0 ms	0 KB	-