Submission #719531

#	Time	Username	Problem	Language	Result	Execution time	Memory
719531		biximo	Knapsack (NOI18_knapsack)	Java	73 / 100	1073 ms	21892 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<item> items = new LinkedList<>();
		for(int i = 0; i < n; i ++) {
			str = new StringTokenizer(in.readLine());
			items.add(new item(Integer.parseInt(str.nextToken()), Integer.parseInt(str.nextToken()), Integer.parseInt(str.nextToken())));
		}
		
		int[] dp = new int[s + 1];
		Arrays.fill(dp, -1);
		dp[0] = 0;
		int max = 0;
		
		while(!items.isEmpty()) {
			item next = items.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]);
					}
				}
			}
		}
		System.out.println(max);

	}
	
	static class item {
		int value, weight, copies;
		item(int value, int weight, int copies) {
			this.value = value;
			this.weight = weight;
			this.copies = copies;
		}
	}

}

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