제출 #330109

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
330109		Agnimandur	Jelly Flavours (IOI20_jelly)	Java	100 / 100	526 ms	241500 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[N+1][x+1];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j <= x; j++) {
				//buy in shop2
				dpX[i+1][j] = dpX[i][j]+vals[i][1];
				
				//buy in shop1
				if (j >= vals[i][0])
					dpX[i+1][j] = Math.min(dpX[i+1][j],dpX[i][j-vals[i][0]]);
			}
		}
		
		
		int[][] dpY = new int[N+1][y+1];
		for (int i = N-1; i >= 0; i--) {
			for (int j = 0; j <= y; j++) {
				//dont take this jelly
				dpY[i][j] = dpY[i+1][j];
				
				//take this jelly
				if (j >= vals[i][1])
					dpY[i][j] = Math.max(dpY[i][j], dpY[i+1][j-vals[i][1]]+1);
			}
		}
		
		int ans = 0;
		for (int i = N; i >= 0; i--) {
			long budget = y-dpX[i][x];
			if (budget >= 0)
				ans = Math.max(ans, i+dpY[i][(int)budget]);
		}
		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