oj.uz

Submission #491229

# Submission time Handle Problem Language Result Execution time Memory
491229 2021-12-01T04:25:20 Z vijay Knapsack (NOI18_knapsack) Java 11
100 / 100
 572 ms 19920 KB 
// 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

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

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 12848 KB Output is correct
2 Correct 113 ms 12652 KB Output is correct
3 Correct 90 ms 12316 KB Output is correct
4 Correct 87 ms 12300 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 8488 KB Output is correct
2 Correct 108 ms 12332 KB Output is correct
3 Correct 103 ms 12428 KB Output is correct
4 Correct 118 ms 12620 KB Output is correct
5 Correct 110 ms 12840 KB Output is correct
6 Correct 139 ms 12732 KB Output is correct
7 Correct 124 ms 13060 KB Output is correct
8 Correct 117 ms 12508 KB Output is correct
9 Correct 111 ms 12576 KB Output is correct
10 Correct 128 ms 12592 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 8488 KB Output is correct
2 Correct 108 ms 12332 KB Output is correct
3 Correct 103 ms 12428 KB Output is correct
4 Correct 118 ms 12620 KB Output is correct
5 Correct 110 ms 12840 KB Output is correct
6 Correct 139 ms 12732 KB Output is correct
7 Correct 124 ms 13060 KB Output is correct
8 Correct 117 ms 12508 KB Output is correct
9 Correct 111 ms 12576 KB Output is correct
10 Correct 128 ms 12592 KB Output is correct
11 Correct 68 ms 8504 KB Output is correct
12 Correct 115 ms 12256 KB Output is correct
13 Correct 103 ms 12368 KB Output is correct
14 Correct 120 ms 12548 KB Output is correct
15 Correct 120 ms 12560 KB Output is correct
16 Correct 115 ms 12704 KB Output is correct
17 Correct 126 ms 12868 KB Output is correct
18 Correct 118 ms 12396 KB Output is correct
19 Correct 116 ms 12548 KB Output is correct
20 Correct 119 ms 12596 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 12848 KB Output is correct
2 Correct 113 ms 12652 KB Output is correct
3 Correct 90 ms 12316 KB Output is correct
4 Correct 87 ms 12300 KB Output is correct
5 Correct 76 ms 8488 KB Output is correct
6 Correct 108 ms 12332 KB Output is correct
7 Correct 103 ms 12428 KB Output is correct
8 Correct 118 ms 12620 KB Output is correct
9 Correct 110 ms 12840 KB Output is correct
10 Correct 139 ms 12732 KB Output is correct
11 Correct 124 ms 13060 KB Output is correct
12 Correct 117 ms 12508 KB Output is correct
13 Correct 111 ms 12576 KB Output is correct
14 Correct 128 ms 12592 KB Output is correct
15 Correct 68 ms 8504 KB Output is correct
16 Correct 115 ms 12256 KB Output is correct
17 Correct 103 ms 12368 KB Output is correct
18 Correct 120 ms 12548 KB Output is correct
19 Correct 120 ms 12560 KB Output is correct
20 Correct 115 ms 12704 KB Output is correct
21 Correct 126 ms 12868 KB Output is correct
22 Correct 118 ms 12396 KB Output is correct
23 Correct 116 ms 12548 KB Output is correct
24 Correct 119 ms 12596 KB Output is correct
25 Correct 71 ms 8332 KB Output is correct
26 Correct 116 ms 12356 KB Output is correct
27 Correct 106 ms 12324 KB Output is correct
28 Correct 104 ms 12684 KB Output is correct
29 Correct 127 ms 12540 KB Output is correct
30 Correct 128 ms 12444 KB Output is correct
31 Correct 117 ms 12636 KB Output is correct
32 Correct 113 ms 12520 KB Output is correct
33 Correct 124 ms 12764 KB Output is correct
34 Correct 143 ms 12472 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 12848 KB Output is correct
2 Correct 113 ms 12652 KB Output is correct
3 Correct 90 ms 12316 KB Output is correct
4 Correct 87 ms 12300 KB Output is correct
5 Correct 76 ms 8488 KB Output is correct
6 Correct 108 ms 12332 KB Output is correct
7 Correct 103 ms 12428 KB Output is correct
8 Correct 118 ms 12620 KB Output is correct
9 Correct 110 ms 12840 KB Output is correct
10 Correct 139 ms 12732 KB Output is correct
11 Correct 124 ms 13060 KB Output is correct
12 Correct 117 ms 12508 KB Output is correct
13 Correct 111 ms 12576 KB Output is correct
14 Correct 128 ms 12592 KB Output is correct
15 Correct 68 ms 8504 KB Output is correct
16 Correct 115 ms 12256 KB Output is correct
17 Correct 103 ms 12368 KB Output is correct
18 Correct 120 ms 12548 KB Output is correct
19 Correct 120 ms 12560 KB Output is correct
20 Correct 115 ms 12704 KB Output is correct
21 Correct 126 ms 12868 KB Output is correct
22 Correct 118 ms 12396 KB Output is correct
23 Correct 116 ms 12548 KB Output is correct
24 Correct 119 ms 12596 KB Output is correct
25 Correct 71 ms 8332 KB Output is correct
26 Correct 116 ms 12356 KB Output is correct
27 Correct 106 ms 12324 KB Output is correct
28 Correct 104 ms 12684 KB Output is correct
29 Correct 127 ms 12540 KB Output is correct
30 Correct 128 ms 12444 KB Output is correct
31 Correct 117 ms 12636 KB Output is correct
32 Correct 113 ms 12520 KB Output is correct
33 Correct 124 ms 12764 KB Output is correct
34 Correct 143 ms 12472 KB Output is correct
35 Correct 460 ms 18836 KB Output is correct
36 Correct 572 ms 19172 KB Output is correct
37 Correct 527 ms 19308 KB Output is correct
38 Correct 562 ms 19240 KB Output is correct
39 Correct 548 ms 19324 KB Output is correct
40 Correct 501 ms 19868 KB Output is correct
41 Correct 492 ms 19588 KB Output is correct
42 Correct 507 ms 19568 KB Output is correct
43 Correct 536 ms 19752 KB Output is correct
44 Correct 478 ms 19664 KB Output is correct
45 Correct 459 ms 19632 KB Output is correct
46 Correct 372 ms 19320 KB Output is correct
47 Correct 536 ms 19780 KB Output is correct
48 Correct 488 ms 19824 KB Output is correct
49 Correct 409 ms 18968 KB Output is correct
50 Correct 470 ms 19920 KB Output is correct