Submission #165076

#	Time	Username	Problem	Language	Result	Execution time	Memory
165076		Berted	Dango Maker (JOI18_dango_maker)	C++14	13 / 100	3 ms	504 KiB

dango_maker

#include <iostream>
#include <queue>
#include <vector>
#define pii pair<int,int>
#define fst first
#define snd second
using namespace std;
int n,m,to=0,dp[3001][4]={};string mp[3001]={};
bool bt[3001][3001][2]={},actv[3001][2]={};
queue<pii> q;
inline bool ck(int y,int x,int dr)
{
	if (y>=0 && y<n-(dr?2:0) && x>=0 && x<m-((!dr)?2:0))
	{
		return mp[y][x] == 'R' && mp[y+dr][x+(!dr)] == 'G' && mp[y+2*dr][x+2*(!dr)] == 'W';
	} 
	else {return 0;}
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for (int i=0;i<n;i++) {cin>>mp[i];}
	for (int i=0;i<n;i++)
	{
		for (int j=0;j<m;j++)
		{
			if (ck(i,j,0) && !bt[i][j][0])
			{
				int mn = 1e9,mx = 0;
				q.emplace(i,j);
				while (!q.empty())
				{
					pii dt = q.front();q.pop();
					for (int i=0;i<3;i++)
					{
						if (!bt[dt.fst][dt.snd][0])
						{
							bt[dt.fst][dt.snd][0] = 1;
							actv[dt.fst][0] = 1;
							mn = min(dt.fst+1,mn);
							mx = max(dt.fst+1,mx);
							//cout<<dt.fst<<","<<dt.snd<<" 0 activated\n";
							for (int i=0;i<3;i++)
							{
								if (ck(dt.fst-i,dt.snd+i,1))
								{
									if (!bt[dt.fst-i][dt.snd+i][1])
									{
										bt[dt.fst-i][dt.snd+i][1] = 1;
										mn = min(dt.fst-i+1,mn);
										mx = max(dt.fst-i+1,mx);
										//cout<<dt.fst-i<<","<<dt.snd+i<<" 1 activated\n";
										actv[dt.fst-i][1] = 1;
										for (int j=0;j<3;j++)
										{
											if (j==i) {continue;}
											if (ck(dt.fst-i+j,dt.snd+i-j,0))
											{
												q.emplace(dt.fst-i+j,dt.snd+i-j);
											}
										}
									}
									
								}
							}
						}
					}
				}
				dp[mn-1][0] = dp[mn-1][1] = dp[mn-1][2] = dp[mn-1][3] = 0;
				for (int i=mn;i<=mx;i++)
				{
					dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
					dp[i][1] = dp[i-1][2];
					dp[i][2] = dp[i-1][3];
					if (actv[i-1][1])
					{
						dp[i][3] = max(dp[i][0],max(dp[i][2],dp[i][1])) + 1;
					}
					if (actv[i-1][0])
					{
						dp[i][0]++;
					}
					//cout<<i<<" 0 -> "<<dp[i][0]<<"\n";
					//cout<<i<<" 1 -> "<<dp[i][1]<<"\n";
					//cout<<i<<" 2 -> "<<dp[i][2]<<"\n";
					//cout<<i<<" 3 -> "<<dp[i][3]<<"\n";
					actv[i-1][0] = actv[i-1][1] = 0;
				}
				to+=max(dp[mx][0],max(dp[mx][1],max(dp[mx][3],dp[mx][2])));
				j+=2;
			}
		}
	}
	for (int i=0;i<n;i++)
	{
		for (int j=0;j<m;j++)
		{
			if (ck(i,j,1) && !bt[i][j][1]) {to++;}
		}
	}
	cout<<to<<"\n";
	return 0;
}

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