Submission #892919

#	Time	Username	Problem	Language	Result	Execution time	Memory
892919		iskhakkutbilim	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	237 ms	58900 KiB

dango_maker

#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;
}

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