Submission #725719

#	Time	Username	Problem	Language	Result	Execution time	Memory
725719		sushikid	Knapsack (NOI18_knapsack)	Java	100 / 100	803 ms	59732 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());
        HashMap<Integer, ArrayList<int[]>> weights = new HashMap<>(); //weight with respect to [price, amount]
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(r.readLine());
            int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); int c = Integer.parseInt(st.nextToken());
            if(!weights.containsKey(b)){
                weights.put(b, new ArrayList<>());
            }
            weights.get(b).add(new int[]{a, c});
        }
        long[][] ans = new long[weights.size() + 1][s + 1];
        for (int i = 0; i < ans.length; i++) {
            Arrays.fill(ans[i], Long.MIN_VALUE);
        }
        ans[0][0] = 0;
        long max = 0;
        int z = 1;
        for(int e : weights.keySet()){
            ArrayList<int[]> possible = weights.get(e);
            Collections.sort(possible, (a, b) -> -Integer.compare(a[0], b[0]));
            for (int i = 0; i <= s; i++) {
                ans[z][i] = ans[z - 1][i];
                int cur = 0;
                int at = 0;
                int total = 0;
                long profit = 0;
                while(i - (total + 1) * e >= 0 && cur < possible.size()){
                    total ++;
                    profit += possible.get(cur)[0];
                    if(ans[z - 1][i - total * e] != Long.MIN_VALUE){
                        ans[z][i] = Math.max(ans[z][i], ans[z - 1][i - total * e] + profit);
                        max = Math.max(ans[z][i], max);
                    }
                    at ++;
                    if(at == possible.get(cur)[1]){
                        at = 0;
                        cur ++;
                    }
                }
            }
            z++;
        }
        pw.println(max);
        pw.close();
    }
}

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