QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#95620 | #6308. Magic | wyzwyz | ML | 0ms | 0kb | C++14 | 825b | 2023-04-10 21:44:41 | 2023-04-10 21:44:45 |
Judging History
answer
#include<cstdio>
#include<cctype>
#include<bitset>
#define maxn 5555
template<class T>
inline T read(){
T r=0,f=0;
char c;
while(!isdigit(c=getchar()))f|=(c=='-');
while(isdigit(c))r=(r<<1)+(r<<3)+(c^48),c=getchar();
return f?-r:r;
}
int n,l[maxn],r[maxn],mat[maxn];
std::bitset<maxn> nvis,to[maxn];
bool dfs(int u){
for(int i=(to[u]&nvis)._Find_first();i<=n;i=(to[u]&nvis)._Find_next(i)){
nvis[i]=1;
if(!mat[i]||dfs(mat[i]))
return mat[i]=u,true;
}
return false;
}
int main(){
n=read<int>();
for(int i=1;i<=n;i++){
l[i]=read<int>();
r[i]=read<int>();
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(l[i]<l[j]&&l[j]<r[i]&&r[i]<r[j])
to[i][j]=1;
int ans=2*n;
for(int i=1;i<=n;i++)
nvis.set(),ans-=dfs(i);
printf("%d\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Memory Limit Exceeded
input:
5 2 3 6 7 1 9 5 10 4 8