Submission #599092

#	Time	Username	Problem	Language	Result	Execution time	Memory
599092		jmyszka2007	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	224 ms	123972 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
char tab[3010][3010];
int dp[3010][3010][2];
int ans[3010][3010];
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	n += 2;
	m += 2;
	for(int i = 3; i <= n; i++) {
		for(int j = 3; j <= m; j++) {
			cin >> tab[i][j];
		}
	}
	for(int i = 3; i <= n; i++) {
		for(int j = 3; j <= m; j++) {
			dp[i][j][0] = dp[i - 1][j + 1][0];
			dp[i][j][1] = dp[i - 1][j + 1][1];
			if(tab[i][j] == 'R' && tab[i][j + 1] == 'G' && tab[i][j + 2] == 'W') {
				if(max(dp[i - 1][j + 1][0], dp[i - 3][j + 3][1]) + 1 > dp[i][j][0]) {
					dp[i][j][0] = max(dp[i - 1][j + 1][0], dp[i - 3][j + 3][1]) + 1;
				}
			}
			if(tab[i][j] == 'R' && tab[i + 1][j] == 'G' && tab[i + 2][j] == 'W') {
				if(max(dp[i - 1][j + 1][0], dp[i - 1][j + 1][1]) + 1 > dp[i][j][1]) {
					dp[i][j][1] = max(dp[i - 1][j + 1][0], dp[i - 1][j + 1][1]) + 1;
				}
			}
			ans[i][j] = max(dp[i][j][0], dp[i][j][1]);
		}
	}
	int res = 0;
	for(int i = 3; i <= n; i++) {
		res += ans[i][3];
	}
	for(int j = 4; j <= m; j++) {
		res += ans[n][j];
	}
	cout << res << '\n';
}

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