Submission #751436

#	Time	Username	Problem	Language	Result	Execution time	Memory
751436		Callie	Knapsack (NOI18_knapsack)	Java	12 / 100	81 ms	10480 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] - y[1]);
		}
		
//		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];
		boolean[] visited = new boolean[budget + 1];
		visited[0] = true;
		
		for(int i = 1; i <= budget; i++) {
			int total = 0;
			for(int[] item: adj[i]) {
				int first = item[0];
				int second = item[1];
				
				for(int j = 0; j < second; j++) {
					total += i;
					if(total > budget) break;
					
					for(int k = budget; k >= i; k--) {
						if(visited[k - i]) {
							dp[k] = Math.max(dp[k], dp[k-i] + first);
							visited[k] = true;
						}
					}
				}
			}
		}
		
		int max = 0;
		for(int i = 1; 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: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27