#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <functional>
#include <utility>
typedef unsigned long long ull;
using namespace std;
vector<vector<int> > cl,ho;
vector<int> match(1001);
bool buy(int u,bitset<1001> &seen){
int a=cl[u][0],p=cl[u][1];
vector<vector<int> >::iterator it=upper_bound(ho.begin(),ho.end(),cl[u],[](const vector<int> &l,const vector<int> &r){
if(l[0]<r[0])
return true;
if(l[0]==r[0]&&l[1]<r[1])
return true;
return false;
});
while(it!=ho.end()){
if((*it)[1]<=p&&!seen[it-ho.begin()]){
seen[it-ho.begin()]=1;
if(!match[it-ho.begin()]||buy(match[it-ho.begin()],seen)){
match[it-ho.begin()]=u;
return true;
}
}
it++;
}
return false;
}
int main(){
int n,h;
cin>>n>>h;
cl.push_back({0,0});
ho.push_back({0,0});
for(int i=0;i<n;i++){
int a,p;
cin>>a>>p;
cl.push_back({a,p});
}
for(int i=0;i<h;i++){
int a,p;
cin>>a>>p;
ho.push_back({a,p});
}
sort(cl.begin(),cl.end(),[](auto &l,auto &r){
if(l[0]<r[0])
return true;
if(l[0]==r[0]&&l[1]<r[1])
return true;
return false;
});
sort(ho.begin(),ho.end(),[](auto &l,auto &r){
if(l[0]<r[0])
return true;
if(l[0]==r[0]&&l[1]<r[1])
return true;
return false;
});
int ans=0;
for(int i=1;i<=n;i++){
bitset<1001> seen;
if(buy(i,seen))
ans++;
// cout<<ans<<endl;
}
cout<<ans<<endl;
return 0;
}
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <functional>
#include <utility>
typedef unsigned long long ull;
using namespace std;
vector<vector<int> > cl,ho;
vector<int> match(1001);
bool buy(int u,bitset<1001> &seen){
int a=cl[u][0],p=cl[u][1];
vector<vector<int> >::iterator it=upper_bound(ho.begin(),ho.end(),cl[u],[](const vector<int> &l,const vector<int> &r){
if(l[0]<r[0])
return true;
if(l[0]==r[0]&&l[1]<r[1])
return true;
return false;
});
while(it!=ho.end()){
if((*it)[1]<=p&&!seen[it-ho.begin()]){
seen[it-ho.begin()]=1;
if(!match[it-ho.begin()]||buy(match[it-ho.begin()],seen)){
match[it-ho.begin()]=u;
return true;
}
}
it++;
}
return false;
}
int main(){
int n,h;
cin>>n>>h;
cl.push_back({0,0});
ho.push_back({0,0});
for(int i=0;i<n;i++){
int a,p;
cin>>a>>p;
cl.push_back({a,p});
}
for(int i=0;i<h;i++){
int a,p;
cin>>a>>p;
ho.push_back({a,p});
}
sort(cl.begin(),cl.end(),[](auto &l,auto &r){
if(l[0]<r[0])
return true;
if(l[0]==r[0]&&l[1]<r[1])
return true;
return false;
});
sort(ho.begin(),ho.end(),[](auto &l,auto &r){
if(l[0]<r[0])
return true;
if(l[0]==r[0]&&l[1]<r[1])
return true;
return false;
});
int ans=0;
for(int i=1;i<=n;i++){
bitset<1001> seen;
if(buy(i,seen))
ans++;
// cout<<ans<<endl;
}
cout<<ans<<endl;
return 0;
}
Comments
Post a Comment