Submission #751608

#	Time	Username	Problem	Language	Result	Execution time	Memory
751608		Callie	Knapsack (NOI18_knapsack)	Java	100 / 100	675 ms	21492 KiB

knapsack

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

public class knapsack {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		
		int budget = Integer.parseInt(st.nextToken());
		int items = Integer.parseInt(st.nextToken());
		ArrayList<int[]>[] adj = new ArrayList[2001];
		
		for(int i = 0; i <= 2000; i++) {
			adj[i] = new ArrayList<int[]>();
		}
		
		for(int i = 0; i < items; i++) {
			st = new StringTokenizer(in.readLine());
			int value = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			int copy = Integer.parseInt(st.nextToken());
			
			adj[weight].add(new int[] {value, copy});
		}
		
		for(int i = 1; i <= 2000; i++) {
			Collections.sort(adj[i], (x, y) -> y[0] - x[0]);
		}
		
//		for(int i = 1; i < 2000; i++) {
//			for(int[] j: adj[i]) {
//				System.out.print("[" + j[0] + ", " + j[1] + "] ");
//			}
//			System.out.println();
//		}
		
		int[] dp = new int[budget + 1];
		Arrays.fill(dp, -1);
		dp[0] = 0;
		
		for(int i = 1; i <= budget; i++) {
			if(adj[i].isEmpty()) continue;
			
			int total = 0;
			for(int item = 0; item < adj[i].size(); item++) {
				
				for(int j = 0; j < adj[i].get(item)[1] && total <= budget; j++) {
					total += i;
					
					for(int k = budget; k >= i; k--) {
						if(dp[k-i] >= 0) {
							dp[k] = Math.max(dp[k], dp[k-i] + adj[i].get(item)[0]);
						}
					}
				}
			}
		}
		
		int max = 0;
		for(int i = 0; i <= budget; i++) {
			max = Math.max(max, dp[i]);
		}
		
		System.out.println(max);
	}
}

Compilation message (stderr)

Note: knapsack.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

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