Pagini recente » Cod sursa (job #1291538) | Cod sursa (job #2093411) | Cod sursa (job #2093414) | Cod sursa (job #2093408) | Cod sursa (job #1682844)
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int64 unsigned long long
#define INF numeric_limits<int64>::max()
#define lsb(x) (-x)&x
using namespace std;
ifstream in("cuplaje.in");
ofstream out("cuplaje.out");
vector< vector<int> > adj;
vector<int> gr1,gr2,fpref,bpref;
map< pair<int,int> , int > M;
vector<bool> v;
int n,m;
int pairup(int x)
{
if(v[x])return 0;
v[x]=true;
for(auto it: adj[x])
if(gr2[it]==0)
{
gr1[x]=it;
gr2[it]=x;
return 1;
}
for(auto it: adj[x])
if(pairup(gr2[it])==1)
{
gr1[x]=it;
gr2[it]=x;
return 1;
}
return 0;
}
int main()
{
in>>n>>m;
adj=vector< vector<int> > (n+1);
gr1=bpref=vector<int> (n+1);
gr2=fpref=vector<int> (m+1);
for(int i=1;i<=n;i++)
in>>bpref[i];
for(int i=1;i<=m;i++)
in>>fpref[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=bpref[i];j++)
if(fpref[j]>=i)
adj[i].pb(j);
for(int ok=1;ok!=0;)
{
ok=0;
v=vector<bool>(n+1);
for(int i=1;i<=n;i++)
if(gr1[i]==0)
ok+=pairup(i);
}
int cnt=0;
for(int i=1;i<=n;i++)
if(gr1[i]!=0)
cnt++;
out<<cnt<<'\n';
return 0;
}