Submission #719532

#	Time	Username	Problem	Language	Result	Execution time	Memory
719532		biximo	Knapsack (NOI18_knapsack)	Java	100 / 100	806 ms	59748 KiB

knapsack

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

public class knapsack {
	public static void main(String[] args) throws IOException {
		BufferedReader read =
		    new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer initial = new StringTokenizer(read.readLine());
		int limit = Integer.parseInt(initial.nextToken());
		int typeNum = Integer.parseInt(initial.nextToken());
		HashMap<Integer, ArrayList<int[]>> byWeight = new HashMap<>();
		for (int t = 0; t < typeNum; t++) {
			StringTokenizer item = new StringTokenizer(read.readLine());
			int value = Integer.parseInt(item.nextToken());
			int weight = Integer.parseInt(item.nextToken());
			int amt = Integer.parseInt(item.nextToken());
			if (weight <= limit && amt > 0) {
				if (!byWeight.containsKey(weight)) {
					byWeight.put(weight, new ArrayList<>());
				}
				byWeight.get(weight).add(new int[] {value, amt});
			}
		}

		/*
		 * best[i][j] contains the most value we can
		 * get using j weight and the first i weight types
		 */
		long[][] best = new long[byWeight.size() + 1][limit + 1];
		for (long[] row : best) { Arrays.fill(row, Integer.MIN_VALUE); }
		best[0][0] = 0;
		int at = 1;
		for (var pair : byWeight.entrySet()) {
			int w = pair.getKey();
			ArrayList<int[]> items = pair.getValue();
			// sort items in reverse order by value
			items.sort(Comparator.comparingInt(i -> - i[0]));
			for (int i = 0; i <= limit; i++) {
				best[at][i] = best[at - 1][i];
				int copies = 0;
				int typeAt = 0;
				int currUsed = 0;
				long profit = 0;
				// go through as many items until we run out of items or usable
				// weight
				while ((copies + 1) * w <= i && typeAt < items.size()) {
					copies++;
					profit += items.get(typeAt)[0];
					if (best[at - 1][i - copies * w] != Integer.MIN_VALUE) {
						best[at][i] = Math.max(
						    best[at][i], best[at - 1][i - copies * w] + profit);
					}
					currUsed++;
					if (currUsed == items.get(typeAt)[1]) {
						currUsed = 0;
						typeAt++;
					}
				}
			}
			at++;
		}

		long mostValue = 0;
		for (int i = 0; i <= limit; i++) {
			mostValue = Math.max(mostValue, best[byWeight.size()][i]);
		}
		System.out.println(mostValue);
	}
}

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