Submission #1136831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136831		b1t_exe	Knapsack (NOI18_knapsack)	Java	73 / 100	1102 ms	163804 KiB

knapsack

import java.util.*;

public class knapsack {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = 1; // Number of test cases

        while (t-- > 0) {
            int x = sc.nextInt(); // Maximum weight capacity
            int n = sc.nextInt(); // Number of items
            int[][] arr = new int[n][3]; // Item details: value, weight, max quantity

            for (int i = 0; i < n; i++) {
                arr[i][0] = sc.nextInt(); // Value of item
                arr[i][1] = sc.nextInt(); // Weight of item
                arr[i][2] = sc.nextInt(); // Maximum quantity of item
            }

            int[] dp = new int[x + 1]; // DP array to store max profit for each capacity

            // Process each item
            for (int i = 0; i < n; i++) {
                int value = arr[i][0];
                int weight = arr[i][1];
                int maxQuantity = arr[i][2];

                // Process for bounded quantity
                for (int capacity = x; capacity >= weight; capacity--) {
                    for (int quantity = 1; quantity <= maxQuantity && quantity * weight <= capacity; quantity++) {
                        dp[capacity] = Math.max(dp[capacity], quantity * value + dp[capacity - quantity * weight]);
                    }
                }
            }

            System.out.println(dp[x]); // Maximum profit for capacity x
        }
        sc.close();
    }
}

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