Submission #1254241

#TimeUsernameProblemLanguageResultExecution timeMemory
1254241minhphanKnapsack (NOI18_knapsack)Java
73 / 100
1101 ms38748 KiB
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] = Math.min(einleser.nextInt(), S / W[i]); } int[] dp = new int[S + 1]; dp[0] = 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 = S - weight; j >= 0; j--) { int newIndex = j + weight; dp[newIndex] = Math.max(dp[newIndex], dp[j] + value); } 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())); } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...