Submission #332174

#	Time	Username	Problem	Language	Result	Execution time	Memory
332174		MahdiBahramian	Dango Maker (JOI18_dango_maker)	C++11	13 / 100	1 ms	364 KiB

dango_maker

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int Max = 3e3 + 10;

struct V
{
	int i , j , b;
};

int dp[Max];
bool seen[Max][Max][2];
char C[Max][Max];

bool ok(V x)
{
	int i = x.i , j = x.j , v = x.b;
	if(i < 0 || j < 0) return false;
	if(!v) return C[i][j] == 'R' && C[i][j + 1] == 'G' && C[i][j + 2] == 'W';
	else  return C[i][j] == 'R' && C[i + 1][j] == 'G' && C[i + 2][j] == 'W';
}

vector<V> N(V a)
{
	if(a.b)
	{
		vector<V> Ne;
		if(ok(V{a.i , a.j , false})) 
			Ne.pb(V{a.i , a.j , false});
		if(ok(V{a.i + 1 , a.j - 1 , false}))
			Ne.pb(V{a.i + 1, a.j - 1 , false});
		if(ok(V{a.i + 2 , a.j - 2 , false}))
			Ne.pb(V{a.i + 2, a.j - 2 , false});
		return Ne;
	}
	else
	{
		vector<V> Ne;
		if(ok(V{a.i , a.j , true})) 
			Ne.pb(V{a.i , a.j , true});
		if(ok(V{a.i - 1 , a.j + 1 , true}))
			Ne.pb(V{a.i - 1, a.j + 1 , true});
		if(ok(V{a.i - 2 , a.j + 2 , true}))
			Ne.pb(V{a.i - 2, a.j + 2 , true});
		return Ne;
	}
}

void DFS(V v1 , V v2 , int i)
{
	seen[v1.i][v1.j][v1.b] = true;
	if(v2.i >= 0)
		seen[v2.i][v2.j][v2.b] = true;

	vector<V> U;
	vector<V> Ne = N(v1);
	for(V u : Ne) if(!seen[u.i][u.j][u.b]) U.pb(u);
	if(U.size() == 0)
	{
		dp[i] = 1 + int(v2.i >= 0);
		dp[i + 1] = 0;
	}
	else if(U.size() == 1)
	{
		DFS(U[0] , V{-1 , -1 , 0} , i + 1);
		dp[i] = max(dp[i + 1] , dp[i + 2] + 1 + int(v2.i >= 0));

	}
	else if(U.size() == 2)
	{
		DFS(U[0] , U[1] , i + 1);
		dp[i] = max(dp[i + 1] , dp[i + 2] + 1);

	}
}

int n , m;



int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for(int i = 0; i < n ; i++)
	{
		for(int j = 0; j < m ; j++)
		{
			cin >> C[i][j];
		}
	}
	
	//0 yani ofoghi 
	//1 yani amodi

	int ans = 0;
	for(int i = 0; i < n ; i++)
	{
		for(int j = 0; j < m ; j++)
		{
			for(int b = 0; b < 2; b++)
			{
				if(ok(V{i , j , b}) && !seen[i][j][b])
				{
					vector<V> Ne = N(V{i , j , b});
					if(Ne.size() == 0) ans++;
					else if(Ne.size() == 1)
					{
						DFS(V{i , j , b} , V{-1,-1,0} , 0);
						ans += dp[0];
					}
					else if(Ne.size() == 2 && N(Ne[0]).size() == 2 && N(Ne[1]).size() == 2)
					{
						DFS(V{i , j , b} , V{-1,-1,0} , 0);
						ans += dp[0];
					}
				}
			}
		}
	}

	cout << ans << '\n';
}

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