Submission #165066

#	Time	Username	Problem	Language	Result	Execution time	Memory
165066		Berted	Dango Maker (JOI18_dango_maker)	C++14	0 / 100	2 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][3]={};string mp[3001]={};
bool bt[3001][3001][2]={},actv[3001][2]={};
queue<pii> q;
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()
{
	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])
			{
				for (int i=0;i<=n;i++)
				{
					actv[i][0] = actv[i][1] = 0;
					dp[i][0] = dp[i][1] = dp[i][2] = 0;
				}
				int to1 = 0,to2 = 0;
				q.push({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;
							//cout<<dt.fst<<","<<dt.snd<<" 0 activated\n";
							to1++;
							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])
									{
										to2 ++;
										bt[dt.fst-i][dt.snd+i][1] = 1;
										//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.push({dt.fst-i+j,dt.snd+i-j});
											}
										}
									}
									
								}
							}
						}
					}
				}
				for (int i=1;i<=n;i++)
				{
					dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
					dp[i][1] = dp[i-1][2];
					dp[i][2] = 0;
					if (actv[i-1][1])
					{
						dp[i][2] = max(dp[i][0],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";
				}
				to+=max(dp[n][0],max(dp[n][1],dp[n][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: 0 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 67