Submission #1144973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144973		uranium235	Knapsack (NOI18_knapsack)	Java	73 / 100	1099 ms	86184 KiB

knapsack

//package ojuz;

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

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]);

        List<int[]> items = new ArrayList<>();
        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);
            if (k == 1) {
                items.add(new int[] {v, w});
                continue;
            }

            int log = 31 - Integer.numberOfLeadingZeros(k);
            for (int j = 0; j < log; j++) {
//                System.out.println(log);
                items.add(new int[] {v << j, w << j});
            }

            int mult = k - (1 << log) + 1;
//            System.out.println("mult: " + mult);
            items.add(new int[] {v * mult, w * mult});
        }

//        System.out.println(items.stream().map(Arrays::toString).collect(Collectors.toList()));

        long[] dp = new long[s + 1];
        for (int[] item : items) {
            for (int i = s; i >= item[1]; i--) {
                dp[i] = Math.max(dp[i], dp[i - item[1]] + item[0]);
            }
        }
        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