Submission #719519

#	Time	Username	Problem	Language	Result	Execution time	Memory
719519		biximo	Knapsack (NOI18_knapsack)	Java	37 / 100	1083 ms	9028 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];
		dp[0] = 0;
		int max = 0;
		while(!items.isEmpty()) {
			item next = items.poll();
			for(int a = 0; a < next.copies; a ++) {
				for(int b = s; b >= 0; b --) {
					if(b + next.weight <= s) {
						dp[b + next.weight] = Math.max(dp[b + next.weight], dp[b] + next.value);
						max = Math.max(max, dp[b + 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: 0 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27