Submission #1254283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254283		minhphan	Knapsack (NOI18_knapsack)	Java	73 / 100	1094 ms	56340 KiB

knapsack

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

/**
 * @since 06.08.2025
 */
public final class knapsack {

    public static void main(String[] args) {
        Einleser einleser = new Einleser();
        int S = einleser.nextInt();
        int N = einleser.nextInt();

        Map<Integer, Data> datas = new HashMap<>();

        for (int i = 0; i < N; i++) {
            int v = einleser.nextInt();
            int w = einleser.nextInt();
            int k = einleser.nextInt();
            Data data = datas.getOrDefault(w, new Data(w));
            data.add(S, v, k);
            datas.put(w, data);
        }

        //Falls zwei Items den gleichen Wert und Gewicht haben, soll ihre Anzahl addiert werden
        //Falls es praktisch unendlich Items gibt und der Wert am größten ist, sollen
        //alle andere Items entfernt werden.
        //


        int[] dp = new int[S + 1];
        dp[0] = 0;

        for (Data data : datas.values()) {
            int weight = data.weight;
            for(DataEntry entry : data.entryList) {
                int amountUsed = entry.amount;
                int value = entry.value;
                if(((long)weight*amountUsed)>=S) {//unbounded knapsack
                    for (int j = weight; j <= S; j++) {
                        dp[j] = Math.max(dp[j], dp[j-weight] + value);
                    }
                } else { //0-1 knapsack
                    int k = 1;
                    while(amountUsed > 0) { //binary
                        int use = Math.min(k, amountUsed);
                        int currentWeight = weight*use;
                        int currentValue = value*use;
                        for (int j = S - currentWeight; j >= 0; j--) {
                            int newIndex = j + currentWeight;
                            dp[newIndex] = Math.max(dp[newIndex], dp[j] + currentValue);
                        }

                        amountUsed -= k;
                        k <<= 1;
                    }
                }
            }
        }

        int globalMax = 0;
        for(int v : dp) {
            if(v > globalMax) {
                globalMax = v;
            }
        }

        einleser.write(String.valueOf(globalMax));
        einleser.close();
    }

    private static class Data {
        private final int weight;
        private int currentAmount;
        private final SortedSet<DataEntry> entryList;

        public Data(int weight) {
            this.weight = weight;
            this.entryList = new TreeSet<>();
        }

        public void add(int S, int value, int amount) {
            int maxAmount = S/this.weight;

            for (DataEntry entry : this.entryList) {
                if (entry.value == value) {
                    entry.amount += amount;
                    this.currentAmount += amount;
                    trimToMax(maxAmount);
                    return;
                }
            }

            // Neuer Eintrag
            this.entryList.add(new DataEntry(value, amount));
            this.currentAmount += amount;
            trimToMax(maxAmount);
        }
        
        private void trimToMax(int maxAmount) {
            if(this.currentAmount > maxAmount) {
                int removed = this.currentAmount - maxAmount;
                DataEntry lowestValue = this.entryList.last();
                while(removed > 0) {
                    if(removed >= lowestValue.amount) {
                        this.entryList.remove(this.entryList.last());
                        removed -= lowestValue.amount;
                        lowestValue = this.entryList.last();
                    } else {
                        lowestValue.amount = lowestValue.amount - removed;
                        removed = 0;
                    }
                }
                this.currentAmount = maxAmount;
            }
        }
    }

    private static class DataEntry implements Comparable<DataEntry> {
        private final int value;
        private int amount;

        private DataEntry(int value, int amount) {
            this.value = value;
            this.amount = amount;
        }

        @Override
        public int compareTo(DataEntry o) {
            return -Integer.compare(this.value, o.value);
        }

        @Override
        public boolean equals(Object o) {
            if (!(o instanceof DataEntry entry)) return false;
            return value == entry.value && amount == entry.amount;
        }

        @Override
        public int hashCode() {
            return Objects.hash(value, amount);
        }
    }

    private static final class Einleser extends PrintWriter {

        private final BufferedReader reader;
        private StringTokenizer tokenizer;

        public Einleser() {
            this(System.in, System.out);
        }

        public Einleser(InputStream i, OutputStream o) {
            super(o);
            reader = new BufferedReader(new InputStreamReader(i));
        }

        public Einleser(String problemName) throws IOException {
            super(problemName + ".out");
            reader = new BufferedReader(new FileReader(problemName + ".in"));
        }

        public String next() {
            try {
                while (tokenizer == null || !tokenizer.hasMoreTokens())
                    tokenizer = new StringTokenizer(reader.readLine());
                return tokenizer.nextToken();
            } catch (Exception e) {
            }
            return null;
        }

        public int nextInt() {
            return Integer.parseInt(Objects.requireNonNull(next()));
        }

        public double nextDouble() {
            return Double.parseDouble(Objects.requireNonNull(next()));
        }

        public long nextLong() {
            return Long.parseLong(Objects.requireNonNull(next()));
        }
    }
}

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