This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define int long long
#define quick ios::sync_with_stdio(0);cin.tie(0);
#define rep(x,a,b) for(int x=a;x<=b;x++)
#define repd(x,a,b) for(int x=a;x>=b;x--)
#define lowbit(x) (x&-x)
#define sz(x) (int)(x.size())
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define mp make_pair
#define eb emplace_back
using namespace std;
typedef pair<int,int> pii;
void debug(){
cout<<"\n";
}
template <class T,class ... U >
void debug(T a, U ... b){
cout<<a<<" ",debug(b...);
}
const int N=3e3+7;
const int INF=1e18;
char c[N][N];
int col[N][N];
int row[N][N];
const int M=3e6+7;
vector<int> v[M];
int my[M];
bool vis[N];
bool dfs(int x){
vis[x]=true;
for(int i:v[x]){
if(my[i]==-1||(!vis[my[i]]&&dfs(my[i]))){
my[i]=x;
return true;
}
}
return false;
}
signed main(){
quick
int n,m;
cin>>n>>m;
rep(i,1,n){
rep(j,1,m) cin>>c[i][j];
}
int Cc=0;
int Cr=0;
rep(i,1,n){
rep(j,1,m){
if(j+2<=m&&c[i][j]=='R'&&c[i][j+1]=='G'&&c[i][j+2]=='W'){
++Cc;
rep(jx,j,j+2){
col[i][jx]=Cc;
}
}
if(i+2<=n&&c[i][j]=='R'&&c[i+1][j]=='G'&&c[i+2][j]=='W'){
++Cr;
rep(ix,i,i+2){
row[ix][j]=Cr;
}
}
}
}
int e=0;
rep(i,1,n){
rep(j,1,m){
if(col[i][j]&&row[i][j]){
v[col[i][j]].eb(row[i][j]);
e++;
}
}
}
fill(my,my+Cr+1,-1);
int ans=0;
rep(i,1,Cc){
ans+=dfs(i);
fill(vis,vis+Cc+1,0LL);
}
cout<<Cr+Cc-ans<<"\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |