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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |