제출 #467840

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
467840		rainliofficial	Knapsack (NOI18_knapsack)	Java	73 / 100	1095 ms	19372 KiB

knapsack

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

public class knapsack {
    static int maxW, n;
    static TreeMap<Integer, ArrayList<Item>> arr;
    public static void main(String[] args) throws IOException{
        BufferedReader file = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader file = new BufferedReader(new FileReader("file.in"));
        StringTokenizer st = new StringTokenizer(file.readLine());
        maxW = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        arr = new TreeMap<>();
        for (int i=0; i<n; i++){
            st = new StringTokenizer(file.readLine());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            if (!arr.containsKey(w)){
                arr.put(w, new ArrayList<>());
            }
            arr.get(w).add(new Item(v, w, k));
        }
        long[] dp = new long[maxW+1];
        long[] pdp = new long[maxW+1];
        for (int currW : arr.keySet()){
            ArrayList<Item> curr = arr.get(currW);
            Collections.sort(curr, (a, b) -> b.val-a.val);
            int iters = maxW/currW;
            for (int j=0; j<iters && j < curr.size(); j++){
                Item currItem = curr.get(j);
                for (int i=1; i<=maxW; i++){
                    dp[i] = pdp[i];
                    for (int k=1; currItem.weight*k<=i && k <= currItem.k; k++){
                        if (i >= (long)currItem.weight*k){
                            dp[i] = Math.max(dp[i], pdp[i-currItem.weight*k] + (long)currItem.val*k);
                        }
                    }
                }
                for (int k=0; k<=maxW; k++){
                    pdp[k] = dp[k];
                    dp[k] = 0;
                }
            }
        }
        System.out.println(pdp[maxW]);
    }
    static class Item{
        int val, weight, k;
        public Item(int val, int weight, int k){
            this.val = val;
            this.weight = weight;
            this.k = k;
        }
    }
}

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