Submission #491229

#	Time	Username	Problem	Language	Result	Execution time	Memory
491229		vijay	Knapsack (NOI18_knapsack)	Java	100 / 100	572 ms	19920 KiB

knapsack

// Source: https://usaco.guide/general/io

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

class Kattio extends PrintWriter {
	private BufferedReader r;
	private StringTokenizer st = new StringTokenizer("");
	private String token;

	// standard input
	public Kattio() { this(System.in,System.out); }
	public Kattio(InputStream i, OutputStream o) {
		super(o);
		r = new BufferedReader(new InputStreamReader(i));
	}
	// USACO-style file input
	public Kattio(String problemName) throws IOException { 
		super(new FileWriter(problemName+".out"));
		r = new BufferedReader(new FileReader(problemName+".in"));
	}

	private String peek() {
		if (token == null)
			try {
				while (!st.hasMoreTokens()) {
					String line = r.readLine();
					if (line == null) return null;
					st = new StringTokenizer(line);
				}
				token = st.nextToken();
			} catch (IOException e) { }
		return token;
	}
	public boolean hasMoreTokens() { return peek() != null; }
	private String next() {
		String ans = peek(); 
		token = null;
		return ans;
	}
	
	public int nextInt() { return Integer.parseInt(next()); }
	public double nextDouble() { return Double.parseDouble(next()); }
	public long nextLong() { return Long.parseLong(next()); }
}

public class knapsack {
	static Kattio io = new Kattio();
	public static void main(String[] args) {
		int S = io.nextInt();
		int N = io.nextInt();

		int[] current = new int[N];
		ArrayList<Product>[] withWeight = new ArrayList[S + 1];
		for(int i = 0; i <= S; i++){
			withWeight[i] = new ArrayList<>();
		}
		int[] values = new int[N];
		
		for(int i = 0; i < N; i++){
			int V = io.nextInt();
			int W = io.nextInt();
			int K = io.nextInt();
			current[i] = K;
			withWeight[W].add(new Product(V, K, W));
			values[i] = V;
		}

		for(int i = 1; i <= S; i++){
			Collections.sort(withWeight[i]);
		}

		long[] dp = new long[S + 1];

		// System.out.println(withWeight[1]);

		long[] prevDp = new long[S + 1];

		for(int w = 1; w <= S; w++){
			int weightIndex = 0;
			long sumPrice = 0;
			for(int count = 1; count <= S / w; count++){
				if(weightIndex >= withWeight[w].size()){
					break;
				}

				sumPrice += withWeight[w].get(weightIndex).price;
				withWeight[w].get(weightIndex).quantity--;
				if(withWeight[w].get(weightIndex).quantity == 0){
					weightIndex++;
				}

				for(int i = count*w; i <= S; i++){
					if(prevDp[i - count*w] + sumPrice > dp[i]){
						dp[i] = Math.max(dp[i], prevDp[i - count*w] + sumPrice);
						// System.out.println("setting " + i + " to: " + " " + dp[i] + " with prev " + dp[i - count*w] + " and " + sumPrice + " prev index " + (i - count*w) + " weight index: " + weightIndex + " with weight " + w);
					}
				}
			}

			for(int i = 0; i <= S; i++){
				dp[i] = Math.max(dp[i], prevDp[i]);
			}

			prevDp = dp;
			dp = new long[S + 1];
		}

		// System.out.println(Arrays.toString(prevDp));

		long max = 0;
		for(int i = 0; i <= S; i++){
			max = Math.max(prevDp[i], max);
		}

		System.out.println(max);
	}

	public static class Product implements Comparable<Product> {
		int price, quantity, weight;
		public Product(int price, int quantity, int weight){
			this.price = price;
			this.quantity = quantity;
			this.weight = weight;
		}

		public int compareTo(Product p){
			return p.price - price;
		}

		public String toString(){
			return "price: " + price + " quantity: " + quantity + " weight: " + weight;
		}
	}
}

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