Submission #1180407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180407		miniob	Dango Maker (JOI18_dango_maker)	C++20	100 / 100	128 ms	10304 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;

string tab[3007];
int dp[3007][4];
int n, m;

bool czyok(int i, int j)
{
	if(i >= 0 && i < n && j >= 0 && j < m)
	{
		return true;
	}
	return false;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int odp = 0;
	cin >> n >> m;
	for(int i = 0; i < n; i++)
	{
		cin >> tab[i];
	}
	for(int i = 0; i < n + m - 3; i++)
	{
		int maxj = min(i + 2, m);
		for(int j = 1; j <= maxj; j++)
		{
			dp[j][0] = max(dp[j - 1][0], max(dp[j - 1][1], dp[j - 1][2]));
			if(czyok(i + 2 - j, j - 2) && tab[i + 2 - j][j - 2] == 'R' && czyok(i + 2 - j, j - 1) && tab[i + 2 - j][j - 1] == 'G' && czyok(i + 2 - j, j) && tab[i + 2 - j][j] == 'W')
			{
				//cout << "tu" << endl;
				dp[j][1] = max(dp[j - 1][0], dp[j - 1][1]) + 1;
			}
			else
			{
				dp[j][1] = 0;
			}
			if(czyok(i + 1 - j, j - 1) && tab[i + 1 - j][j - 1] == 'R' && czyok(i + 2 - j, j - 1) && tab[i + 2 - j][j - 1] == 'G' && czyok(i + 3 - j, j - 1) && tab[i + 3 - j][j - 1] == 'W')
			{
				//cout << "tu" << endl;
				dp[j][2] = max(dp[j - 1][0], dp[j - 1][2]) + 1;
			}
			else
			{
				dp[j][2] = 0;
			}
		//	cout << dp[j + 1][0] << " " << dp[j + 1][1] << " " << dp[j + 1][2] << endl;
		}
		//cout << dp[maxj][0] << " " << dp[maxj][1] << " " << dp[maxj][2] << endl;
		odp += max(dp[maxj][0], max(dp[maxj][1], dp[maxj][2]));
	}
	cout << odp << endl;
	return 0;
}

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