Submission #679644

#	Time	Username	Problem	Language	Result	Execution time	Memory
679644		nicolexxuu	Knapsack (NOI18_knapsack)	Java	100 / 100	557 ms	21236 KiB

knapsack

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

public class knapsack {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int S = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		
		ArrayList<Pair>[] items = new ArrayList[S+1];
		for(int i = 0; i <= S; i++) items[i] = new ArrayList<>();
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int V = Integer.parseInt(st.nextToken());
			int W = Integer.parseInt(st.nextToken());
			int K = Integer.parseInt(st.nextToken());
			items[W].add(new Pair(V, K));
		}
		br.close();
		
		for(int i = 0; i <= S; i++) Collections.sort(items[i], (a, b) -> b.a - a.a);
	
		long[] dp = new long[S+1];
		for(int w = 1; w <= S; w++) {
//			System.out.println("w: " + w);
			for(int s = S; s >= 1; s--) {
				int currI = 0, currCnt = 0, val = 0;
				for(int cnt = 1; cnt * w <= s && currI < items[w].size(); cnt++) {
					val += items[w].get(currI).a;
					if(++currCnt == items[w].get(currI).b) {
						currCnt = 0;
//						System.out.println("cnt: " + cnt + " incremeneting currI");
						currI++;
					}
					dp[s] = Math.max(dp[s], dp[s-cnt*w] + val);
				}
			}
			
//			for(int s = 0; s <= S; s++)
//				System.out.print(dp[s] + " ");
//			System.out.println();
		}
		
		System.out.println(dp[S]);
	}
	
	public static class Pair{
		int a, b;
		Pair(int a, int b) {
			this.a = a;
			this.b = b;
		}
	}
}

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