Submission #1254220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254220		minhphan	Knapsack (NOI18_knapsack)	Java	73 / 100	1096 ms	38276 KiB

knapsack

import java.io.*;
import java.util.Arrays;
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] = einleser.nextInt();
        }

        int[] dp = new int[S + 1];
        Arrays.fill(dp, -1);
        dp[0] = 0;

        int globalMax = 0;

        for (int i = 0; i < N; i++) {
            int weight = W[i];
            int value = V[i];
            int copy = Math.min(K[i], S/weight);
            for (int copies = 0; copies<copy; copies++) {
                for (int j = S - weight; j >= 0; j--) {
                    if(dp[j] != -1) {
                        dp[j + weight] = Math.max(dp[j + weight], dp[j] + value);
                        if(dp[j + weight] > globalMax) {
                            globalMax = dp[j + weight];
                        }
                    }
                }
            }
        }

        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