Submission #303894

#TimeUsernameProblemLanguageResultExecution timeMemory
303894pit4hDango Maker (JOI18_dango_maker)C++14
33 / 100
256 ms262148 KiB
#include<bits/stdc++.h>
using namespace std;
const int N = 3001;
int n, m, nr;
int matched[N * N], vis[N * N], rep[N][N];
int iter;
bool horiz[N][N], vert[N][N];
string tab[N];
vector<int> g[N * N];
bool match(int x) {
	vis[x] = iter;
	for(int i: g[x]) {
		if(matched[i] == -1) {
			matched[i] = x;
			return true;
		}
	}
	for(int i: g[x]) {
		if(vis[matched[i]] != iter && match(matched[i])) {
			matched[i] = x;
			return true;
		}
	}
	return false;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i=n-1; i>=0; --i) {
		cin>>tab[i];
	}
	for(int i=0; i<n; ++i) { // left - right
		for(int j=0; j+2<m; ++j) {
			if(tab[i][j] == 'R' && tab[i][j+1] == 'G' && tab[i][j+2] == 'W') {
				vert[i][j] = 1;
			}
		}
	}
	for(int i=2; i<n; ++i) { // top - bottom 
		for(int j=0; j<m; ++j) {
			if(tab[i][j] == 'R' && tab[i-1][j] == 'G' && tab[i-2][j] == 'W') {
				horiz[i][j] = 1;
				rep[i][j] = nr;
				nr++;
			}
		}
	}
	int sz = 0;
	for(int i=0; i<n; ++i) {
		for(int j=0; j<m; ++j) {
			if(vert[i][j]) {
				if(horiz[i][j]) {
					g[sz].push_back(rep[i][j]);
				}
				if(i+1<n && j+1<m && horiz[i+1][j+1]) {
					g[sz].push_back(rep[i+1][j+1]);
				}
				if(i+2<n && j+2<m && horiz[i+2][j+2]) {
					g[sz].push_back(rep[i+2][j+2]);
				}
				sz++;
			}
		}
	}
	for(int i=0; i<nr; ++i) {
		matched[i] = -1;
	}
	int ans = 0;
	for(int i=0; i<sz; ++i) {
		iter++;
		match(i);
	}
	for(int i=0; i<nr; ++i) {
		if(matched[i] != -1) {
			ans++;
		}
	}
	cout<<nr + sz - ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...