Submission #91391

#	Time	Username	Problem	Language	Result	Execution time	Memory
91391		aminra	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	254 ms	113528 KiB

dango_maker

//tavakol bar khoda
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = (int)3e3 + 3;
const int MOD = (int)1e9 + 7;
const int infint = (int)1e8 + 3;
const ll inf = (ll)1e18;
int n, m, dp[MAXN][4];
char c[MAXN][MAXN];
int satri(int i, int j)
{
	return j < m - 2 && c[i][j] == 'R' && c[i][j + 1] == 'G' && c[i][j + 2] == 'W';
}
int sotuni(int i, int j)
{
	return i < n - 2 && c[i][j] == 'R' && c[i + 1][j] == 'G' && c[i + 2][j] == 'W';
}
int MAX(int idx)
{
	return max(max(dp[idx][0], dp[idx][1]), max(dp[idx][2], dp[idx][3]));
}
int main()
{
	ios::sync_with_stdio(false);
	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];
	int ans = 0;
	for (int i = 0; i < m; i++)
	{
		int mx = 0;
		memset(dp, 0, sizeof dp);
		if(satri(0, i))
			dp[0][0] = 1;
		else
		if(sotuni(0, i))
			dp[0][1] = 1;
		mx = MAX(0);
		for (int j = 1; j < n && i - j >= 0; j++)
		{
			//(j, i - j)
			dp[j][0] = max(dp[j - 1][2], dp[j - 1][0] + satri(j, i - j));
			dp[j][2] = max(dp[j - 1][1], dp[j - 1][3]);
			dp[j][1] = max(dp[j - 1][0], dp[j - 1][2]) + sotuni(j, i - j);
			dp[j][3] = max(dp[j - 1][1], dp[j - 1][3]) + sotuni(j, i - j);
			mx = max(mx, MAX(j));
		}
		ans += mx;
	}
	for (int i = 1; i < n; i++)
	{
		int mx = 0;
		memset(dp, 0, sizeof dp);
		if(sotuni(i, m - 1))
			dp[0][1] = 1;
		mx = MAX(0);
		for (int j = 1; j + i < n && m - 1 - j >= 0; j++)
		{
			//(j + i, m - 1 - j)
			dp[j][0] = max(dp[j - 1][2], dp[j - 1][0] + satri(j + i, m - 1 - j));
			dp[j][2] = max(dp[j - 1][1], dp[j - 1][3]);
			dp[j][1] = max(dp[j - 1][0], dp[j - 1][2]) + sotuni(j + i, m - 1 - j);
			dp[j][3] = max(dp[j - 1][1], dp[j - 1][3]) + sotuni(j + i, m - 1 - j);
			mx = max(mx, MAX(j));
		}
		ans += mx;
	}
	cout << ans;
}

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