QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#699988 | #6308. Magic | Idtwtei | ML | 0ms | 0kb | C++14 | 1.2kb | 2024-11-02 11:29:35 | 2024-11-02 11:29:36 |
answer
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5,INF=1e9;
#define gc getchar()
#define rd read()
inline int read(){
int x=0,f=0; char c=gc;
for(;c<'0'||c>'9';c=gc) f|=(c=='-');
for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+(c^48);
return f?-x:x;
}
int n,s,t,l[N],r[N];
bitset<N*2> G[N*2];
bitset<N*2> dis; queue<int> q;
int bfs(){
for(int i=1;i<=t;++i) dis[i]=0;
while(!q.empty()) q.pop(); q.push(s),dis[s]=1;
while(!q.empty()){
int u=q.front(); q.pop();
for(int v=G[u]._Find_first();v<=t;v=G[u]._Find_next(v)){
if(!dis[v]){
dis[v]=1,q.push(v);
if(v==t) return 1;
}
}
}
return 0;
}
int dinic(int u,int df){
if(u==t) return df;
int res=df;
for(int v=G[u]._Find_first(),k;res&&v<=t;v=G[u]._Find_next(v)){
if(dis[v]){
k=dinic(v,1);
if(!k) dis[v]=0;
else G[u][v]=0,G[v][u]=1,--res;
}
}
return df-res;
}
int main(){
n=rd,s=2*n+1,t=2*n+2;
for(int i=1;i<=n;++i) G[s][l[i]=rd]=1,G[r[i]=rd][t]=1;
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]) G[l[i]][r[j]]=1;
int dflow=0,maxflow=0;
while(bfs()) while(dflow=dinic(s,INF)) maxflow+=dflow;
printf("%d\n", 2*n-maxflow);
return 0;
}
详细
Test #1:
score: 0
Memory Limit Exceeded
input:
5 2 3 6 7 1 9 5 10 4 8