제출 #330107

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
330107		Agnimandur	Jelly Flavours (IOI20_jelly)	Java	100 / 100	319 ms	13428 KiB

jelly

import java.util.*;
class jelly {
	int find_maximum_unique(int x, int y, int[] a, int[] b) {
		int N = a.length;
		int[][] vals = new int[N][2];
		for (int i = 0; i < N; i++)
			vals[i] = new int[] {a[i],b[i]};
		sort(vals);
		
		long[] dpX = new long[x+1];
		long[] budget = new long[N];
		for (int i = 0; i < N; i++) {
			long[] dpXnew = new long[x+1];
			for (int j = 0; j <= x; j++) {
				//buy in shop2
				dpXnew[j] = dpX[j]+vals[i][1];
				
				//buy in shop1
				if (j >= vals[i][0])
					dpXnew[j] = Math.min(dpXnew[j],dpX[j-vals[i][0]]);
			}
			dpX = dpXnew;
			budget[i] = y-dpX[x];
		}
		
		int ans = 0;
		int[] dpY = new int[y+1];
		for (int i = N-1; i >= 0; i--) {
			if (budget[i] >= 0)
				ans = Math.max(ans, i+1+dpY[(int)budget[i]]);
			
			int[] dpYnew = new int[y+1];
			for (int j = 0; j <= y; j++) {
				//dont take this jelly
				dpYnew[j] = dpY[j];
				
				//take this jelly
				if (j >= vals[i][1])
					dpYnew[j] = Math.max(dpYnew[j], dpY[j-vals[i][1]]+1);
			}
			dpY = dpYnew;
		}
		ans = Math.max(ans, dpY[y]);
		return ans;
	}
	
	void sort(int[][] arr) {
		//Sort an array (immune to quicksort TLE)
		Random rgen = new Random();
		for (int i = 0; i < arr.length; i++) {
			int randomPosition = rgen.nextInt(arr.length);
			int[] temp = arr[i];
			arr[i] = arr[randomPosition];
			arr[randomPosition] = temp;
		}
		Arrays.sort(arr, new Comparator<int[]>() {
			@Override
			public int compare(int[] arr1, int[] arr2) {
				return arr1[0]-arr2[0];
				//Ascending order.
			}
		});
	}
}

• Subtask 1: 11 / 11
• Subtask 2: 24 / 24
• Subtask 3: 9 / 9
• Subtask 4: 10 / 10
• Subtask 5: 14 / 14
• Subtask 6: 32 / 32