Submission #992168

#	Time	Username	Problem	Language	Result	Execution time	Memory
992168		sushikid	Knapsack (NOI18_knapsack)	Java	73 / 100	1062 ms	33096 KiB

knapsack

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

public class knapsack {
    public static void main(String[] args) throws IOException{
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        
        StringTokenizer st = new StringTokenizer(r.readLine());
        int s = Integer.parseInt(st.nextToken()); int n = Integer.parseInt(st.nextToken());
        int[][] info = new int[n][3];
        long ans = -1;
        long[] weight = new long[s + 1];
            Arrays.fill(weight, Integer.MIN_VALUE);
            weight[0] = 0;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(r.readLine());
            info[i][0] = Integer.parseInt(st.nextToken()); 
            info[i][1] = Integer.parseInt(st.nextToken()); 
            info[i][2] = Math.min(s/info[i][1], Integer.parseInt(st.nextToken()));
        }
        for (int[] e : info) {
            for (int i = s; i >= e[1]; i--) {
                for (int j = e[2]; j > 0; j--) {
                    if(i - j * e[1] < 0){
                        continue;
                    }
                    weight[i] = Math.max(weight[i], weight[i - j * e[1]] + e[0] * j);
                }
            }
        }
        for(long e : weight){
            ans = Math.max(e, ans);
        }
        pw.println(ans);
        pw.close();
    }
}

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