Submission #257561

#	Time	Username	Problem	Language	Result	Execution time	Memory
257561		groeneprof	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	756 ms	36984 KiB

dango_maker

#include <bits/stdc++.h>
#define P(x) do {if(debug) cout << x << endl;} while(false)
#define H(x) P(#x << ": " << x)
#define FR(i, a, b) for(int i = (a); i < (b); ++i)
#define F(i, n) FR(i, 0, n)
#define DR(i, a, b) for(int i = (b); i --> (a);)
#define D(i, n) DR(i, 0, n)
#define S(s) (int)(s).size()
#define ALL(x) (x).begin(), (x).end()
#define MI(x, a) (x) = min(x, a)
#define MA(x, a) (x) = max(x, a)
#define V vector
#define pb push_back
#define mp make_pair
using namespace std;
const bool debug = 0;
const int inf = 1e9;
int N,M;

vector<string> A;
bool vis[3002][3002][2];
bool isRGW(int x, int y, bool vh){ /*0 is horizontal 1 is vertical*/
	if(x-vh>=0 && x+vh<N && y-1+vh>=0 && y+1-vh<M){
		if(vh==0) return A[x][y] == 'G' && A[x][y-1] == 'R' && A[x][y+1] == 'W';
		else return A[x][y] == 'G' && A[x-1][y] == 'R' && A[x+1][y] == 'W';
	}
	return false;
}

bool isleaf(int x, int y, bool vh){
	return isRGW(x,y,vh) && isRGW(x,y,!vh) + isRGW(x-1,y+1,!vh) + isRGW(x+1,y-1,!vh) <= 1;
}
int v; int h;
void dfs(int x, int y, bool vh){
	if(!isRGW(x,y,vh) || vis[x][y][vh]){
		return;
	}
	vis[x][y][vh] = true;
	if(vh){
		v++;
	}
	else{
		h++;
	}
	dfs(x,y,!vh);
	dfs(x+1,y-1,!vh);
	dfs(x-1,y+1,!vh);
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>N>>M;
	
	A.resize(N);
	F(i,N){
		cin>>A[i];
	}
	int ans = 0;
	F(i,N) F(j,M) F(b,2){
		if(isleaf(i,j,b)){
			H(i);
			H(j);
			H(b);
			A[i][j] = '0';
			A[i+b][j+1-b] = '0';
			A[i-b][j-1+b] = '0';
			P("a");
			ans++;
		}	
	}

	F(j,M) F(i,N) F(b,2){
		if(isleaf(i,j,b)){
			H(i);
			H(j);
			H(b);
			A[i][j] = '0';
			A[i+b][j+1-b] = '0';
			A[i-b][j-1+b] = '0';
			ans++;
		}	
	}
	F(i,N) F(j,M) F(b,2){
		v = 0; h = 0;
		dfs(i,j,b);
		ans+=max(v,h);
	}
	cout<<ans<<endl;
	return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 67 / 67