제출 #892919

#제출 시각아이디문제언어결과실행 시간메모리
892919iskhakkutbilimDango Maker (JOI18_dango_maker)C++17
100 / 100
237 ms58900 KiB
#include <bits/stdc++.h>
using namespace std;

#define all(a) a.begin(), a.end()

const int N = 3e3;
char a[N+5][N+5];
int n, m;




signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	vector<int> dio[n + m + 2];
	
	for(int i = 1;i <= n; i++){
		for(int j = 1;j <= m; j++){
			cin >> a[i][j];
			dio[i + j].push_back(i);
		}
	}
	int ans = 0;
	for(int sum = 2;sum < n + m + 1; sum++){
		int sz = dio[sum].size();
		int dp[sz + 2][3];
		memset(dp, 0, sizeof(dp));
		int idx = 1;
		for(int i : dio[sum]){
			int j = sum - i;
			dp[idx][0] = max({dp[idx-1][0], dp[idx-1][1], dp[idx-1][2]});
			if(a[i][j] == 'G' && j - 1 > 0 && a[i][j-1] == 'R' && j + 1 <= m && a[i][j+1] == 'W'){
				dp[idx][1] = max({dp[idx-1][0], dp[idx-1][1]}) + 1;
			}
			if(a[i][j] == 'G' && i - 1 > 0 && a[i-1][j] == 'R' && i + 1 <= n && a[i + 1][j] == 'W'){
				dp[idx][2] = max({dp[idx-1][0], dp[idx-1][2]}) + 1;
			}
			idx++;
		}
		
		ans += max({dp[sz][0], dp[sz][1], dp[sz][2]});
	}
	cout << ans;
	
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...