Submission #1219973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219973		brito.joao	Knapsack (NOI18_knapsack)	Java	0 / 100	52 ms	11344 KiB

knapsack

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

class Knapsack {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int S = Integer.parseInt(st.nextToken()); // max weight
        int N = Integer.parseInt(st.nextToken()); // number of item types
        
        List<Item> items = new ArrayList<>();
        
        // Read items and expand using binary lifting for large quantities
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int value = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            int count = Integer.parseInt(st.nextToken());
            
            // Binary lifting: break down large quantities into powers of 2
            int k = 1;
            while (k < count) {
                items.add(new Item(value * k, weight * k));
                count -= k;
                k *= 2;
            }
            if (count > 0) {
                items.add(new Item(value * count, weight * count));
            }
        }
        
        // Standard 0/1 knapsack DP on the expanded items
        long[] dp = new long[S + 1];
        
        for (Item item : items) {
            // Traverse backwards to avoid using the same item multiple times
            for (int w = S; w >= item.weight; w--) {
                dp[w] = Math.max(dp[w], dp[w - item.weight] + item.value);
            }
        }
        
        System.out.println(dp[S]);
    }
    
    static class Item {
        long value;
        int weight;
        
        Item(long value, int weight) {
            this.value = value;
            this.weight = weight;
        }
    }
}

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