Submission #537905

#	Time	Username	Problem	Language	Result	Execution time	Memory
537905		tkwiatkowski	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	376 ms	84892 KiB

dango_maker

/*
	Zadanie: Dango Maker
	Autor: Tomasz Kwiatkowski
*/

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back

using namespace std;
typedef long long ll;

const int MAXN = 3e3 + 7;
const int INF = 1e9 + 7;

char color[MAXN][MAXN];
pair<int, int> dp[MAXN][MAXN];

pair<int, int> RGW(int i, int j)
{
	pair<int, int> res = {false, false};
	if (color[i][j] == 'R' && color[i][j+1] == 'G' && color[i][j+2] == 'W')
		res.fi = true;
	if (color[i][j] == 'R' && color[i+1][j] == 'G' && color[i+2][j] == 'W')
		res.se = true;
	return res;
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);

	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j)
			cin >> color[i][j];
	}

	int ans = 0;
	for (int j = 1; j <= m; ++j) {
		pair<int, int> prv = {0, 0};
		for (int i = 1; i <= min(n, j); ++i) {
			auto [h, v] = RGW(i, j - i + 1);
			// printf("[%d, %d]\t", h, v);
			dp[i][j - i + 1].fi = dp[i - 1][j - i + 1 + 1].fi + h;
			dp[i][j - i + 1].se = max(dp[i - 1][j - i + 1 + 1].fi, dp[i - 1][j - i + 1 + 1].se) + v;
			if (i >= 3) {
				dp[i][j - i + 1].fi = max(dp[i][j - i + 1].fi, dp[i - 3][j - i + 1 + 3].se + h);
			}
			// printf("dp[%d][%d] = (%d, %d)\n", i, j - i + 1, dp[i][j - i + 1].fi, dp[i][j - i + 1].se);
			prv = dp[i][j - i + 1];
		}
		ans += max(prv.fi, prv.se);
	}
	for (int i = 2; i <= n; ++i) {
		pair<int, int> prv = {0, 0};
		for (int j = m; j >= max(m - n + i, 1); --j) {
			auto [h, v] = RGW(i + m - j, j);
			// printf("[%d, %d]\t", h, v);
			dp[i + m - j][j].fi = dp[i + m - j - 1][j + 1].fi + h;
			dp[i + m - j][j].se = max(dp[i + m - j - 1][j + 1].fi, dp[i + m - j - 1][j + 1].se)  + v;
			if (i + m - j >= 3) {
				dp[i + m - j][j].fi = max(dp[i + m - j][j].fi, dp[i + m - j - 3][j + 3].se + h);
			}
			// printf("dp[%d][%d] = (%d, %d)\n", i + m - j, j, dp[i + m - j][j].fi, dp[i + m - j][j].se);
			prv = dp[i + m - j][j];
		}
		ans += max(prv.fi, prv.se);
	}

	cout << ans << '\n';
	return 0;
}

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