Submission #1037985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037985		vako_p	Dango Maker (JOI18_dango_maker)	C++14	0 / 100	1 ms	2396 KiB

dango_maker

#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][2],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){
			dp[i][j][0] = dp[i][j][1] = max(dp[i + 1][j - 1][1], dp[i + 1][j - 1][0]);
		}
		if(a[i][j] != 'R'){
			i--;
			j++;
			continue;
		}
		if(check(i + 1, j, 'G') and check(i + 2, j, 'W')) dp[i][j][1]++;
		if(check(i, j + 1, 'G') and check(i, j + 2, 'W')){
			if(j > 0 and i + 1 < n) dp[i][j][0] = max(dp[i][j][0], dp[i + 1][j - 1][1] + 1);
			else dp[i][j][0] = 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], dp[ii][jj][1]);
//		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], dp[ii][jj][1]);
	}
	cout << ans << '\n';
}

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