oj.uz

Submission #450505

# Submission time Handle Problem Language Result Execution time Memory
450505 2021-08-03T00:35:59 Z SansPapyrus683 Knapsack (NOI18_knapsack) Java 11
100 / 100
 988 ms 58196 KB 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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 && 0 <= amt) {
                if (!byWeight.containsKey(weight)) {
                    byWeight.put(weight, new ArrayList<>());
                }
                byWeight.get(weight).add(new int[] {value, amt});
            }
        }

        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<int[]> items = pair.getValue();
            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 curr_used = 0;
                long profit = 0;
                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
                        );
                    }
                    curr_used++;
                    if (curr_used == items.get(typeAt)[1]) {
                        curr_used = 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 116 ms 8964 KB Output is correct
2 Correct 88 ms 8956 KB Output is correct
3 Correct 113 ms 10392 KB Output is correct
4 Correct 84 ms 8956 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 9092 KB Output is correct
2 Correct 120 ms 10508 KB Output is correct
3 Correct 120 ms 10468 KB Output is correct
4 Correct 99 ms 9244 KB Output is correct
5 Correct 97 ms 9144 KB Output is correct
6 Correct 149 ms 14428 KB Output is correct
7 Correct 140 ms 14304 KB Output is correct
8 Correct 133 ms 14564 KB Output is correct
9 Correct 135 ms 14468 KB Output is correct
10 Correct 141 ms 14292 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 9092 KB Output is correct
2 Correct 120 ms 10508 KB Output is correct
3 Correct 120 ms 10468 KB Output is correct
4 Correct 99 ms 9244 KB Output is correct
5 Correct 97 ms 9144 KB Output is correct
6 Correct 149 ms 14428 KB Output is correct
7 Correct 140 ms 14304 KB Output is correct
8 Correct 133 ms 14564 KB Output is correct
9 Correct 135 ms 14468 KB Output is correct
10 Correct 141 ms 14292 KB Output is correct
11 Correct 92 ms 8976 KB Output is correct
12 Correct 155 ms 11380 KB Output is correct
13 Correct 121 ms 10424 KB Output is correct
14 Correct 98 ms 9112 KB Output is correct
15 Correct 99 ms 9088 KB Output is correct
16 Correct 142 ms 14496 KB Output is correct
17 Correct 138 ms 14468 KB Output is correct
18 Correct 141 ms 14584 KB Output is correct
19 Correct 166 ms 14548 KB Output is correct
20 Correct 137 ms 14416 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 8964 KB Output is correct
2 Correct 88 ms 8956 KB Output is correct
3 Correct 113 ms 10392 KB Output is correct
4 Correct 84 ms 8956 KB Output is correct
5 Correct 92 ms 9092 KB Output is correct
6 Correct 120 ms 10508 KB Output is correct
7 Correct 120 ms 10468 KB Output is correct
8 Correct 99 ms 9244 KB Output is correct
9 Correct 97 ms 9144 KB Output is correct
10 Correct 149 ms 14428 KB Output is correct
11 Correct 140 ms 14304 KB Output is correct
12 Correct 133 ms 14564 KB Output is correct
13 Correct 135 ms 14468 KB Output is correct
14 Correct 141 ms 14292 KB Output is correct
15 Correct 92 ms 8976 KB Output is correct
16 Correct 155 ms 11380 KB Output is correct
17 Correct 121 ms 10424 KB Output is correct
18 Correct 98 ms 9112 KB Output is correct
19 Correct 99 ms 9088 KB Output is correct
20 Correct 142 ms 14496 KB Output is correct
21 Correct 138 ms 14468 KB Output is correct
22 Correct 141 ms 14584 KB Output is correct
23 Correct 166 ms 14548 KB Output is correct
24 Correct 137 ms 14416 KB Output is correct
25 Correct 87 ms 9028 KB Output is correct
26 Correct 136 ms 10560 KB Output is correct
27 Correct 118 ms 10348 KB Output is correct
28 Correct 93 ms 9020 KB Output is correct
29 Correct 93 ms 9204 KB Output is correct
30 Correct 142 ms 14420 KB Output is correct
31 Correct 131 ms 14608 KB Output is correct
32 Correct 130 ms 14608 KB Output is correct
33 Correct 131 ms 14580 KB Output is correct
34 Correct 141 ms 14336 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 8964 KB Output is correct
2 Correct 88 ms 8956 KB Output is correct
3 Correct 113 ms 10392 KB Output is correct
4 Correct 84 ms 8956 KB Output is correct
5 Correct 92 ms 9092 KB Output is correct
6 Correct 120 ms 10508 KB Output is correct
7 Correct 120 ms 10468 KB Output is correct
8 Correct 99 ms 9244 KB Output is correct
9 Correct 97 ms 9144 KB Output is correct
10 Correct 149 ms 14428 KB Output is correct
11 Correct 140 ms 14304 KB Output is correct
12 Correct 133 ms 14564 KB Output is correct
13 Correct 135 ms 14468 KB Output is correct
14 Correct 141 ms 14292 KB Output is correct
15 Correct 92 ms 8976 KB Output is correct
16 Correct 155 ms 11380 KB Output is correct
17 Correct 121 ms 10424 KB Output is correct
18 Correct 98 ms 9112 KB Output is correct
19 Correct 99 ms 9088 KB Output is correct
20 Correct 142 ms 14496 KB Output is correct
21 Correct 138 ms 14468 KB Output is correct
22 Correct 141 ms 14584 KB Output is correct
23 Correct 166 ms 14548 KB Output is correct
24 Correct 137 ms 14416 KB Output is correct
25 Correct 87 ms 9028 KB Output is correct
26 Correct 136 ms 10560 KB Output is correct
27 Correct 118 ms 10348 KB Output is correct
28 Correct 93 ms 9020 KB Output is correct
29 Correct 93 ms 9204 KB Output is correct
30 Correct 142 ms 14420 KB Output is correct
31 Correct 131 ms 14608 KB Output is correct
32 Correct 130 ms 14608 KB Output is correct
33 Correct 131 ms 14580 KB Output is correct
34 Correct 141 ms 14336 KB Output is correct
35 Correct 617 ms 19316 KB Output is correct
36 Correct 693 ms 19404 KB Output is correct
37 Correct 705 ms 19380 KB Output is correct
38 Correct 731 ms 19716 KB Output is correct
39 Correct 655 ms 19632 KB Output is correct
40 Correct 853 ms 51492 KB Output is correct
41 Correct 813 ms 58104 KB Output is correct
42 Correct 843 ms 58012 KB Output is correct
43 Correct 959 ms 58196 KB Output is correct
44 Correct 988 ms 58124 KB Output is correct
45 Correct 735 ms 25892 KB Output is correct
46 Correct 424 ms 21176 KB Output is correct
47 Correct 844 ms 27340 KB Output is correct
48 Correct 987 ms 38636 KB Output is correct
49 Correct 571 ms 21800 KB Output is correct
50 Correct 654 ms 21872 KB Output is correct