Submission #456391

#	Time	Username	Problem	Language	Result	Execution time	Memory
456391		SansPapyrus683	Knapsack (NOI18_knapsack)	Java	73 / 100	1028 ms	58168 KiB

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 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27