Submission #1179443

#TimeUsernameProblemLanguageResultExecution timeMemory
1179443vibhasExhibition (JOI19_ho_t2)Java
50 / 100
204 ms339968 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];
        Picture[] pictures = new Picture[n];
        int[] frames = new int[m];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                already_calculated[i][j] = -1;
            }
        }
        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));
    }
    public static int recursive(int picture_index, int frame_index, Picture[] pic, int[]fra, int[][] memo) {
        if ((picture_index >= pic.length) || (frame_index >= fra.length)) {
            return 0;
        }
        if(! (memo[picture_index][frame_index] == -1)){
            return memo[picture_index][frame_index];
        }
        if(fra[frame_index] >= pic[picture_index].size){
            // choosing both frame and picture and moving the pointers.
            memo[picture_index][frame_index] = 1 + recursive(picture_index + 1, frame_index + 1, pic, fra, memo);
            return memo[picture_index][frame_index];
        }else {
            // move to the next indices on either and see which is better.
            int second_ans = Math.max(recursive(picture_index +1, frame_index, pic, fra, memo), recursive(picture_index, frame_index + 1, pic, fra, memo));
            memo[picture_index][frame_index] = second_ans;
            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...