oj.uz

Submission #456386

# Submission time Handle Problem Language Result Execution time Memory
456386 2021-08-06T15:57:35 Z SansPapyrus683 Knapsack (NOI18_knapsack) Java 11
73 / 100
 1000 ms 59544 KB 
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 91 ms 9220 KB Output is correct
2 Correct 83 ms 9092 KB Output is correct
3 Correct 111 ms 10488 KB Output is correct
4 Correct 85 ms 9160 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 8992 KB Output is correct
2 Correct 115 ms 10264 KB Output is correct
3 Correct 112 ms 10452 KB Output is correct
4 Correct 91 ms 9388 KB Output is correct
5 Correct 99 ms 9148 KB Output is correct
6 Correct 132 ms 14340 KB Output is correct
7 Correct 129 ms 14384 KB Output is correct
8 Correct 131 ms 14444 KB Output is correct
9 Correct 132 ms 14364 KB Output is correct
10 Correct 132 ms 14336 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 8992 KB Output is correct
2 Correct 115 ms 10264 KB Output is correct
3 Correct 112 ms 10452 KB Output is correct
4 Correct 91 ms 9388 KB Output is correct
5 Correct 99 ms 9148 KB Output is correct
6 Correct 132 ms 14340 KB Output is correct
7 Correct 129 ms 14384 KB Output is correct
8 Correct 131 ms 14444 KB Output is correct
9 Correct 132 ms 14364 KB Output is correct
10 Correct 132 ms 14336 KB Output is correct
11 Correct 89 ms 8916 KB Output is correct
12 Correct 146 ms 11212 KB Output is correct
13 Correct 115 ms 10468 KB Output is correct
14 Correct 95 ms 9364 KB Output is correct
15 Correct 90 ms 9028 KB Output is correct
16 Correct 133 ms 14392 KB Output is correct
17 Correct 129 ms 14332 KB Output is correct
18 Correct 133 ms 14420 KB Output is correct
19 Correct 134 ms 14560 KB Output is correct
20 Correct 133 ms 14388 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 9220 KB Output is correct
2 Correct 83 ms 9092 KB Output is correct
3 Correct 111 ms 10488 KB Output is correct
4 Correct 85 ms 9160 KB Output is correct
5 Correct 91 ms 8992 KB Output is correct
6 Correct 115 ms 10264 KB Output is correct
7 Correct 112 ms 10452 KB Output is correct
8 Correct 91 ms 9388 KB Output is correct
9 Correct 99 ms 9148 KB Output is correct
10 Correct 132 ms 14340 KB Output is correct
11 Correct 129 ms 14384 KB Output is correct
12 Correct 131 ms 14444 KB Output is correct
13 Correct 132 ms 14364 KB Output is correct
14 Correct 132 ms 14336 KB Output is correct
15 Correct 89 ms 8916 KB Output is correct
16 Correct 146 ms 11212 KB Output is correct
17 Correct 115 ms 10468 KB Output is correct
18 Correct 95 ms 9364 KB Output is correct
19 Correct 90 ms 9028 KB Output is correct
20 Correct 133 ms 14392 KB Output is correct
21 Correct 129 ms 14332 KB Output is correct
22 Correct 133 ms 14420 KB Output is correct
23 Correct 134 ms 14560 KB Output is correct
24 Correct 133 ms 14388 KB Output is correct
25 Correct 87 ms 9092 KB Output is correct
26 Correct 135 ms 10696 KB Output is correct
27 Correct 113 ms 10416 KB Output is correct
28 Correct 95 ms 9172 KB Output is correct
29 Correct 95 ms 9080 KB Output is correct
30 Correct 140 ms 14512 KB Output is correct
31 Correct 143 ms 14472 KB Output is correct
32 Correct 130 ms 14396 KB Output is correct
33 Correct 130 ms 14540 KB Output is correct
34 Correct 133 ms 14476 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 9220 KB Output is correct
2 Correct 83 ms 9092 KB Output is correct
3 Correct 111 ms 10488 KB Output is correct
4 Correct 85 ms 9160 KB Output is correct
5 Correct 91 ms 8992 KB Output is correct
6 Correct 115 ms 10264 KB Output is correct
7 Correct 112 ms 10452 KB Output is correct
8 Correct 91 ms 9388 KB Output is correct
9 Correct 99 ms 9148 KB Output is correct
10 Correct 132 ms 14340 KB Output is correct
11 Correct 129 ms 14384 KB Output is correct
12 Correct 131 ms 14444 KB Output is correct
13 Correct 132 ms 14364 KB Output is correct
14 Correct 132 ms 14336 KB Output is correct
15 Correct 89 ms 8916 KB Output is correct
16 Correct 146 ms 11212 KB Output is correct
17 Correct 115 ms 10468 KB Output is correct
18 Correct 95 ms 9364 KB Output is correct
19 Correct 90 ms 9028 KB Output is correct
20 Correct 133 ms 14392 KB Output is correct
21 Correct 129 ms 14332 KB Output is correct
22 Correct 133 ms 14420 KB Output is correct
23 Correct 134 ms 14560 KB Output is correct
24 Correct 133 ms 14388 KB Output is correct
25 Correct 87 ms 9092 KB Output is correct
26 Correct 135 ms 10696 KB Output is correct
27 Correct 113 ms 10416 KB Output is correct
28 Correct 95 ms 9172 KB Output is correct
29 Correct 95 ms 9080 KB Output is correct
30 Correct 140 ms 14512 KB Output is correct
31 Correct 143 ms 14472 KB Output is correct
32 Correct 130 ms 14396 KB Output is correct
33 Correct 130 ms 14540 KB Output is correct
34 Correct 133 ms 14476 KB Output is correct
35 Correct 623 ms 20276 KB Output is correct
36 Correct 673 ms 20652 KB Output is correct
37 Correct 680 ms 20124 KB Output is correct
38 Correct 752 ms 20840 KB Output is correct
39 Correct 639 ms 21712 KB Output is correct
40 Correct 831 ms 53348 KB Output is correct
41 Correct 818 ms 59356 KB Output is correct
42 Correct 829 ms 59316 KB Output is correct
43 Correct 917 ms 59388 KB Output is correct
44 Correct 971 ms 59544 KB Output is correct
45 Correct 732 ms 25564 KB Output is correct
46 Correct 426 ms 21080 KB Output is correct
47 Correct 861 ms 27204 KB Output is correct
48 Execution timed out 1045 ms 38464 KB Time limit exceeded
49 Halted 0 ms 0 KB -