Submission #1038012

#TimeUsernameProblemLanguageResultExecution timeMemory
1038012vako_pDango Maker (JOI18_dango_maker)C++14
100 / 100
390 ms229768 KiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int mxN = 3e3 + 5;
ll n,dp[mxN][mxN][3],ii,jj,m;
char a[mxN][mxN];

bool check(ll i, ll j, char ch){
	if(i >= n or i < 0 or j >= m or j < 0) return false;
	return (a[i][j] == ch);
}

void f(ll i, ll j){
	while(i >= 0 and j < m){
		ii = i;
		jj = j;
		if(j > 0 and i + 1 < n){
			ll x = max(dp[i + 1][j - 1][1], dp[i + 1][j - 1][0]);
			dp[i][j][2] = max(x, dp[i + 1][j - 1][2]);
		}
		if(a[i][j] != 'R'){
			i--;
			j++;
			continue;
		}
		// 0 -- > R
		// 1 -- > D 
		// 2 -- > 
		if(check(i + 1, j, 'G') and check(i + 2, j, 'W')){
			if(j > 0 and i + 1 < n){
				dp[i][j][1] = dp[i + 1][j - 1][1] + 1;
			}
			else dp[i][j][1] = 1;
			if(j > 1 and i + 2 < n){
				dp[i][j][1] = max(dp[i][j][1], max(dp[i + 2][j - 2][1], dp[i + 2][j - 2][2]) + 1);
			}
		}
		if(check(i, j + 1, 'G') and check(i, j + 2, 'W')){
			dp[i][j][0] = dp[i][j][2] + 1;
		} 
		i--;
		j++;	
	}
}

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 >> a[i][j];
	}
	ll ans = 0;
	for(int i = 0; i < n; i++){
		f(i, 0);
		ans += max(dp[ii][jj][0], max(dp[ii][jj][1], dp[ii][jj][2]));
//		cout << i << ' ' << ii << ' ' << jj << ' ' << max(dp[ii][jj][0], dp[ii][jj][1]) << '\n';
	}
	for(int j = 1; j < m; j++){
		f(n - 1, j);
		ans += max(dp[ii][jj][0], max(dp[ii][jj][1], dp[ii][jj][2]));
	}
	cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...