Submission #1144884

#TimeUsernameProblemLanguageResultExecution timeMemory
1144884thecrazycandyDango Maker (JOI18_dango_maker)C++20
100 / 100
268 ms163528 KiB
#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace std;
#define sped_up ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
const ll INF = (ll)1e9 + 1, INFL = (ll)1e18 + 1;
const ll mod = (ll)1e9 + 7, MAXN = (ll)3333;
ll dp[MAXN][MAXN][2];
char a[MAXN][MAXN];
int main () {
	sped_up;
	ll n, m;
	cin >> n >> m;
	ll ans = 0;
	for (int i = 4; i <= n + 3; i++) {
		for (int j = 4; j <= m + 3; j++) cin >> a[i][j];
	}
	for (int i = 4; i <= n + 3; i++) {
		ll f = i, s = 4;
		while (f >= 4 && s <= m + 3) {
			ll ok = 0, ok1 = 0;
			if (a[f][s] == 'W' && a[f - 1][s] == 'G' && a[f - 2][s] == 'R') ok = 1;
			if (a[f][s] == 'W' && a[f][s - 1] == 'G' && a[f][s - 2] == 'R') ok1 = 1;
			dp[f][s][1] = max(dp[f + 1][s - 1][0], dp[f + 1][s - 1][1]) + ok;
			dp[f][s][0] = max(dp[f + 3][s - 3][1], dp[f + 1][s - 1][0]) + ok1;
			f--, s++;
		}
		f++, s--;
		ans += max(dp[f][s][0], dp[f][s][1]);
	}
	for (int i = 5; i <= m + 3; i++) {
		ll f = n + 3, s = i;
		while (f >= 4 && s <= m + 3) {
			ll ok = 0, ok1 = 0;
			if (a[f][s] == 'W' && a[f - 1][s] == 'G' && a[f - 2][s] == 'R') ok = 1;
			if (a[f][s] == 'W' && a[f][s - 1] == 'G' && a[f][s - 2] == 'R') ok1 = 1;
			dp[f][s][1] = max(dp[f + 1][s - 1][0], dp[f + 1][s - 1][1]) + ok;
			dp[f][s][0] = max(dp[f + 3][s - 3][1], dp[f + 1][s - 1][0]) + ok1;
			f--, s++;
		}
		f++, s--;
		ans += max(dp[f][s][0], dp[f][s][1]);
	}
	cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...