Submission #824117

#TimeUsernameProblemLanguageResultExecution timeMemory
824117svenDango Maker (JOI18_dango_maker)C++17
100 / 100
294 ms35628 KiB
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3 * 1000 + 10;

char tab[MAXN][MAXN];
bool peut[MAXN][MAXN][2];
// 0 -> droite 
// 1 -> bas
//
int mod3(int n)
{
	return ((n % 3) + 3) % 3;
}
int main()
{
	ios::sync_with_stdio(false);
	int N , M;
	cin >> N >> M;
	for (int i = 0 ; i < N ; i++)
	{
		for (int j = 0 ; j < M ; j++)
		{
			cin >> tab[i][j];
		}
	}
	for (int i = 0 ; i < N ; i++)
	{
		for (int j = 0 ; j < M ; j++)
		{
			if (j + 2 < M && tab[i][j] == 'R' && tab[i][j + 1] == 'G' && tab[i][j + 2] == 'W')
			{
				peut[i][j][0] = true;
			}
			if (i + 2 < N && tab[i][j] == 'R' && tab[i + 1][j] == 'G' && tab[i + 2][j] == 'W')
			{
				peut[i][j][1] = true;
			}
		}
	}

	int sol = 0;
	int i0 = 0;
	int j0 = 0;
	while (j0 < M && i0 < N)
	{
		int nb[3];
		nb[0] = nb[1] = nb[2] = 0;
		int ofs = 0;
		int i = i0;
		int j = j0;
		while (i < N && j >= 0)
		{
			int valb = max(nb[ofs] , max(nb[mod3(ofs - 1)] , nb[mod3(ofs - 2)])) + 1;
			int vald = nb[ofs] + 1;
			nb[mod3(ofs - 2)] = max(nb[mod3(ofs - 2)] , nb[ofs]);
			nb[mod3(ofs - 1)] = max(nb[mod3(ofs - 1)] , nb[mod3(ofs - 2)]);
			if (peut[i][j][0])
			{
				nb[mod3(ofs - 2)] = max(nb[mod3(ofs - 2)] , vald);
				nb[mod3(ofs - 1)] = max(nb[mod3(ofs - 1)] , vald);
				nb[mod3(ofs - 0)] = max(nb[mod3(ofs - 0)] , vald);
			}
			if (peut[i][j][1])
			{
				nb[ofs] = valb;
			}
//			if (j0 == 7)
//			{
//				cout<<nb[ofs]<<" "<<nb[mod3(ofs - 1)]<<" "<<nb[mod3(ofs - 2)]<<endl;
//			}
			i++;
			j--;
			ofs = mod3(ofs + 1);
		}
		int aj = max(nb[0] , max(nb[1] , nb[2]));
		sol += aj;
//		cout<<aj<<endl;
		j0++;
		if (j0 == M)
		{
			i0++;
			j0 = M - 1;
		}
	}
	cout<<sol<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...