제출 #483927

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
483927		ymm	Dango Maker (JOI18_dango_maker)	C++17	0 / 100	127 ms	262148 KiB

dango_maker

///
///   You fell for it, fool!
///   Thunder Cross Split Attack!
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

const int N = 3010;
int ch, cv;
char a[N][N];
int n, m;
vector<int> A[2*N*N];
bitset<2*N*N> vis;

bool gdh(int i, int j){return 0 <= i && i < n && 0 <= j && j+3 <= m && a[i][j] == 'R' && a[i][j+1] == 'G' && a[i][j+2] == 'W';}
bool gdv(int i, int j){return 0 <= i && i+2 <= n && 0 <= j && j < m && a[i][j] == 'R' && a[i+1][j] == 'G' && a[i+2][j] == 'W';}

pii dfs(int v)
{
	int a = 1, b = 0;
	vis[v] = 1;
	for(int u : A[v]){
		if(vis[u]) continue;
		auto [x, y] = dfs(u);
		a += y; b += x;
	}
	return {a, b};
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	Loop(i,0,n) cin >> a[i];
	Loop(i,0,n) Loop(j,0,n) {
		if(gdh(i,j)){
			if(gdv(i,j)) A[m*i+j].push_back(n*m + m*i+j);
			if(gdv(i-1,j+1)) A[m*i+j].push_back(n*m + m*i+j-m+1);
			if(gdv(i-2,j+2)) A[m*i+j].push_back(n*m + m*i+j-2*m+2);
		} else vis[m*i+j] = 1;
		if(gdv(i,j)){
			if(gdh(i,j)) A[n*m + m*i+j].push_back(m*i+j);
			if(gdh(i+1,j-1)) A[n*m + m*i+j].push_back(m*i+j+m-1);
			if(gdh(i+2,j-2)) A[n*m + m*i+j].push_back(m*i+j+2*m-2);
		} else vis[n*m + m*i+j] = 1;
	}
	int ans = 0;
	Loop(v,0,2*n*m)
	{
		if(vis[v]) continue;
		auto [x, y] = dfs(v);
		ans += max(x, y);
	}
	cout << ans << '\n';
}

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