oj.uz

Submission #799657

# Submission time Handle Problem Language Result Execution time Memory
799657 2023-07-31T18:05:30 Z rocketsri Knapsack (NOI18_knapsack) Java 11
12 / 100
 115 ms 10860 KB 
import java.util.*;
public class knapsack {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int m=in.nextInt(), n=in.nextInt();
		int[] a = new int[n];
		int[] w = new int[n];
		int[] freq = new int[n];
		
		HashMap<Integer, ArrayList<int[]>> pairs = new HashMap<>(); //(weight, {value, frequency})
		for(int i=0; i<n; i++) {
			a[i]=in.nextInt();
			w[i]=in.nextInt();
			freq[i]=in.nextInt();
		}
		
		for(int i=0; i<n; i++) {
			if(pairs.containsKey(w[i])) {
				pairs.get(w[i]).add(new int[] {a[i], freq[i]});
			}
			else {
				pairs.put(w[i], new ArrayList<>(Arrays.asList(new int[] {a[i], freq[i]})));
			}
		}
		
		long[] dp = new long[m+1];
		for(int i=0; i<m+1; i++) {
			dp[i]=-1;
		}
		dp[0]=0;
		
		for(int weight : pairs.keySet()) {
			ArrayList<int[]> curr = pairs.get(weight);
			curr.sort(Comparator.comparingInt(b -> b[b.length-1]));
		}
		
		for(int weight : pairs.keySet()) {
			long sum=0;
			for(int[] j : pairs.get(weight)) {
				sum += j[1];
			}
			for(int i=m; i>=weight; i--) {
				long f = (long)(i/weight);
				if(dp[i-(int)(Math.min(f, sum)*weight)]!=-1) {
					long c = dp[i-(int)(Math.min(f, sum)*weight)];
					for(int[] j : pairs.get(weight)) {
						long fr = j[1], val = j[0];
						if(fr>f) {
							c += f*val;
							f=0;
							break;
						}
						else {
							c += fr*val;
							f -= fr;
						}
					}
					
					dp[i] = Math.max(dp[i], c);
				}
			}

		}
		
		long max=0;
		for(int i=0; i<m+1; i++) {
			max = Math.max(max, dp[i]);
		}
		
		System.out.println(max);
	}

}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 10152 KB Output is correct
2 Correct 87 ms 10160 KB Output is correct
3 Correct 87 ms 10132 KB Output is correct
4 Correct 88 ms 10136 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 115 ms 10860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 115 ms 10860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 10152 KB Output is correct
2 Correct 87 ms 10160 KB Output is correct
3 Correct 87 ms 10132 KB Output is correct
4 Correct 88 ms 10136 KB Output is correct
5 Incorrect 115 ms 10860 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 10152 KB Output is correct
2 Correct 87 ms 10160 KB Output is correct
3 Correct 87 ms 10132 KB Output is correct
4 Correct 88 ms 10136 KB Output is correct
5 Incorrect 115 ms 10860 KB Output isn't correct
6 Halted 0 ms 0 KB -