Submission #1179438

#TimeUsernameProblemLanguageResultExecution timeMemory
1179438vibhasExhibition (JOI19_ho_t2)Java
0 / 100
67 ms13032 KiB
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; import java.util.StringTokenizer; public class joi2019_ho_t2{ public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int[][]already_calculated = new int[n][m]; boolean[][]helper = new boolean[n][m]; Picture[] pictures = new Picture[n]; int[] frames = new int[m]; for(int i = 0; i < n; i++){ st = new StringTokenizer(br.readLine()); pictures[i] = new Picture(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())); } for(int i = 0; i < m; i++){ frames[i] = Integer.parseInt(br.readLine()); } Arrays.sort(pictures, new PictureComp()); Arrays.sort(frames); System.out.println(recursive(0, 0, pictures, frames, already_calculated, helper)); } public static int recursive(int picture_index, int frame_index, Picture[] pic, int[]fra, int[][] memo, boolean[][]help){ if(frame_index == fra.length-1){ if(fra[frame_index] >= pic[picture_index].size){ return 1; }else{ return 0; } } if(picture_index == pic.length-1){ if(fra[frame_index] >= pic[picture_index].size){ return 1; }else{ return 0; } } if(help[picture_index][frame_index]){ return memo[picture_index][frame_index]; } if(fra[frame_index] >= pic[picture_index].size){ memo[picture_index][frame_index]= 1 + recursive(picture_index + 1, frame_index + 1, pic, fra, memo, help); return memo[picture_index][frame_index]; }else { int second_ans = Math.max(recursive(picture_index + 1, frame_index, pic, fra, memo, help), recursive(picture_index, frame_index + 1, pic, fra, memo, help)); memo[picture_index][frame_index] = Math.max(second_ans, recursive(picture_index + 1, frame_index + 1, pic, fra, memo, help)); return memo[picture_index][frame_index]; } } } class Picture{ int size; int value; public Picture(int a, int b){ this.size = a; this.value = b; } } class PictureComp implements Comparator<Picture> { public int compare(Picture p1, Picture p2){ if(p1.value == p2.value){ return p1.size - p2.size; } return p1.value-p2.value; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...