Submission #719536

#	Time	Username	Problem	Language	Result	Execution time	Memory
719536		biximo	Knapsack (NOI18_knapsack)	Java	100 / 100	629 ms	21868 KiB

knapsack

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

public class knapsack {
	static BufferedReader in;
	
	public static void main(String[] args) throws Exception {
		
		in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer str = new StringTokenizer(in.readLine());
		int s = Integer.parseInt(str.nextToken());
		int n = Integer.parseInt(str.nextToken());
		
		LinkedList<Integer> keyset = new LinkedList<>();
		HashMap<Integer, PriorityQueue<item>> items = new HashMap<>();
		for(int i = 0; i < n; i ++) {
			str = new StringTokenizer(in.readLine());
			item item = new item(Integer.parseInt(str.nextToken()), Integer.parseInt(str.nextToken()), Integer.parseInt(str.nextToken()));
			if(!items.containsKey(item.weight)) {
				items.put(item.weight, new PriorityQueue<>());
				keyset.add(item.weight);
			}
			items.get(item.weight).add(item);
		}
		
		int[] dp = new int[s + 1];
		Arrays.fill(dp, -1);
		dp[0] = 0;
		int max = 0;
		
		while(!keyset.isEmpty()) {
			PriorityQueue<item> pqItems = items.get(keyset.poll());
			item next = pqItems.poll();
			Queue<Integer> processNext = new LinkedList<>();
			for(int b = s; b >= 0; b --) {
				if(b + next.weight <= s) {
					if(dp[b + next.weight] < dp[b] + next.value) {
						dp[b + next.weight] = dp[b] + next.value;
						processNext.add(b + next.weight);
					}
					max = Math.max(max, dp[b + next.weight]);
				}
			}
			for(int a = 1; a < next.copies; a ++) {
				int times = processNext.size();
				if(times == 0)
					break;
				for(int b = 0; b < times; b ++) {
					int ind = processNext.poll();
					if(ind + next.weight <= s && dp[ind + next.weight] < dp[ind] + next.value) {
						dp[ind + next.weight] = dp[ind] + next.value;
						processNext.add(ind + next.weight);
						max = Math.max(max, dp[ind + next.weight]);
					}
				}
			}
			while(!pqItems.isEmpty()) {
				next = pqItems.poll();
				int times = -1;
				for(int a = 0; a < next.copies; a ++) {
					times = processNext.size();
					if(times == 0)
						break;
					for(int b = 0; b < times; b ++) {
						int ind = processNext.poll();
						if(ind + next.weight <= s && dp[ind + next.weight] < dp[ind] + next.value) {
							dp[ind + next.weight] = dp[ind] + next.value;
							processNext.add(ind + next.weight);
							max = Math.max(max, dp[ind + next.weight]);
						}
					}
				}
				if(times == 0)
					break;
			}
		}
		System.out.println(max);

	}
	
	static class item implements Comparable<item> {
		int value, weight, copies;
		item(int value, int weight, int copies) {
			this.value = value;
			this.weight = weight;
			this.copies = copies;
		}
		@Override
		public int compareTo(item o) {
			return Integer.compare(o.value, this.value);
		}
	}

}

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