Submission #501934

#	Time	Username	Problem	Language	Result	Execution time	Memory
501934		churros	Knapsack (NOI18_knapsack)	Java	49 / 100	164 ms	16080 KiB

knapsack

import java.io.*;
import java.util.*;

public class knapsack {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int maxWeight = Integer.parseInt(st.nextToken());
        int numItemTypes = Integer.parseInt(st.nextToken());
        HashMap<Integer, ArrayList<int[]>> weightMap = new HashMap<>();
        for (int i = 0; i < numItemTypes; i++) {
            st = new StringTokenizer(br.readLine());
            int value = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            int copies = Integer.parseInt(st.nextToken());
            if (weightMap.containsKey(weight)) {
                weightMap.get(weight).add(new int[] {value, copies});
            } else {
                ArrayList<int[]> itemArray = new ArrayList<>();
                itemArray.add(new int[] {value, copies});
                weightMap.put(weight, itemArray);
            }
        }
        long[][] maxVal = new long[maxWeight + 1][weightMap.size() + 1];
        int currentWeight = 1;
        for (var weightCategory : weightMap.entrySet()) {
            ArrayList<int[]> weightList = weightCategory.getValue();
            int weight = weightCategory.getKey();
            int numWeightsConsidered = 0;
            for (int[] weightMod : weightList) {
                numWeightsConsidered += weightMod[1];
            }
            numWeightsConsidered = Math.min(numWeightsConsidered, maxWeight/weight);
            Collections.sort(weightList, Comparator.comparingInt(j -> -j[0]));
            for (int i = 0; i <= maxWeight; i++) {
                maxVal[i][currentWeight] = Math.max(maxVal[i][currentWeight], maxVal[i][currentWeight - 1]);
                long valAccrued = maxVal[i][currentWeight - 1];
                int totalWeight = i;
                int weightType = 0;
                int j = 0;
//                System.out.println(numWeightsConsidered);
                while(j < numWeightsConsidered) {
                    int numCopies = weightList.get(weightType)[1];
                    while (j < numWeightsConsidered && numCopies > 0) {
//                        System.out.println(i + "weight " + j + " " + maxVal[i][currentWeight-1] + " " + numCopies + " " + weightList.get(weightType)[0] + " " + weight);
                        valAccrued += weightList.get(weightType)[0];
                        totalWeight += weight;
                        if (totalWeight <= maxWeight)
                            maxVal[totalWeight][currentWeight] = Math.max(maxVal[totalWeight][currentWeight], valAccrued);
                        numCopies--;
                        j++;
                    }
                    weightType++;
                    if (totalWeight > maxWeight)
                        break;
                }
            }
            currentWeight++;
        }
        long maxValue = 0;
        int size = weightMap.size();
        for (int i = 0; i <= maxWeight; i++) {
            maxValue = Math.max(maxValue, maxVal[i][size]);
        }
        pw.println(maxValue);

        br.close();
        pw.close();
    }
}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27