Submission #1254229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254229		minhphan	Knapsack (NOI18_knapsack)	Java	73 / 100	1097 ms	38472 KiB

knapsack

import java.io.*;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Objects;
import java.util.StringTokenizer;

/**
 * @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();

        int[] V = new int[N];
        int[] W = new int[N];
        int[] K = new int[N];

        for (int i = 0; i < N; i++) {
            V[i] = einleser.nextInt();
            W[i] = einleser.nextInt();
            K[i] = Math.min(einleser.nextInt(),  S / W[i]);
        }

        BitSet bitSet = new BitSet(S + 1);
        int[] dp = new int[S + 1];
        dp[0] = 0;
        bitSet.set(0);

        int globalMax = 0;

        for (int i = 0; i < N; i++) {
            int amountUsed = K[i];
            int k = 1;
            while(amountUsed > 0) {
                int use = Math.min(k, amountUsed);
                int weight = W[i]*use;
                int value = V[i]*use;
                for (int j = bitSet.previousSetBit(S - weight); j >= 0; j = bitSet.previousSetBit(j - 1)) {
                    int newIndex = j + weight;
                    int newValue = Math.max(dp[newIndex], dp[j] + value);

                    dp[newIndex] = newValue;
                    bitSet.set(newIndex);
                    if (newValue > globalMax) {
                        globalMax = newValue;
                    }
                }

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

        System.out.println(globalMax);
    }

    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