제출 #1144974

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1144974		uranium235	Knapsack (NOI18_knapsack)	Java	73 / 100	1097 ms	46124 KiB

knapsack

//package ojuz;

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

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

        String[] first = reader.readLine().split(" ");
        int s = Integer.parseInt(first[0]), n = Integer.parseInt(first[1]);
        int[] dp = new int[s + 1];

        for (int i = 0; i < n; i++) {
            String[] arr = reader.readLine().split(" ");
            int v = Integer.parseInt(arr[0]), w = Integer.parseInt(arr[1]), k = Integer.parseInt(arr[2]);
            k = Math.min(k, s / w);

            int log = 31 - Integer.numberOfLeadingZeros(k);
            for (int j = 0; j < log; j++) {
                for (int l = s; l >= w; l--) {
                    dp[l] = Math.max(dp[l], dp[l - w] + v);
                }
                w <<= 1;
                v <<= 1;
            }

            int mult = k - (1 << log) + 1;
            w >>= log;
            v >>= log;
            w *= mult;
            v *= mult;
            for (int j = s; j >= w; j--) {
                dp[j] = Math.max(dp[j], dp[j - w] + v);
            }
        }

        System.out.println(dp[s]);
    }
}

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