제출 #1254250

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254250		minhphan	Knapsack (NOI18_knapsack)	Java	0 / 100	48 ms	10592 KiB

knapsack

import java.io.*;
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];
        dp[0] = 0;

        for (int i = 0; i < N; i++) {
            int amountUsed = K[i];
            int weight = W[i];
            int value = V[i];
            if(((long)weight*amountUsed)>=S) {
                for (int j = 0; j <= S; j++) {
                    int newIndex = j + weight;
                    dp[newIndex] = Math.max(dp[newIndex], dp[j] + value);
                }
            } else {
                int k = 1;
                while(amountUsed > 0) {
                    int use = Math.min(k, amountUsed);
                    int currentWeight = weight*use;
                    int currentValue = V[i]*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 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: 0 / 12
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27