Submission #900193

#	Time	Username	Problem	Language	Result	Execution time	Memory
900193		jkwn	Knapsack (NOI18_knapsack)	Java	73 / 100	1054 ms	28164 KiB

knapsack

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

public class knapsack {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer tokenizer = new StringTokenizer(in.readLine());

        int s = Integer.parseInt(tokenizer.nextToken());
        int n = Integer.parseInt(tokenizer.nextToken());
        int[] dp = new int[s+1];
        dp[0] = 1;

        for (int i = 0; i < n; i++) {
            tokenizer = new StringTokenizer(in.readLine());
            int v = Integer.parseInt(tokenizer.nextToken());
            int w = Integer.parseInt(tokenizer.nextToken());
            int k = Integer.parseInt(tokenizer.nextToken());
            for (int j = s; j >= 0; j--) {
                if (dp[j] >= 1) {
                    for (int count = 0; count <= k; count++) {
                        if (j + w * count <= s) {
                            dp[j+w*count] = Math.max(dp[j+w*count], dp[j] + v*count);
                        }
                        else {
                            break;
                        }
                    }
                }
            }
        }
        int ans = 0;
        for (int i = 1; i < s+1; i++) {
            ans = Math.max(ans, dp[i]);
        }
        System.out.println(ans-1);
    }
}

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