Submission #440806

#	Time	Username	Problem	Language	Result	Execution time	Memory
440806		ritul_kr_singh	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	1168 ms	18176 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

const int MAXN = 3e3;

int n, m, dp[3][3];
string g[MAXN+1];

bool up(int i, int j){
	return i > 2 && g[i-2][j] == 'R' && g[i-1][j] == 'G' && g[i][j] == 'W';
}

bool left(int i, int j){
	return j > 2 && g[i][j-2] == 'R' && g[i][j-1] == 'G' && g[i][j] == 'W';
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	for(int i=1; i<=n; ++i) cin >> g[i], g[i] = ' ' + g[i];

	for(int s=2; s<=n+m; ++s){
		int i = max(1LL, s - m);
		for(; i<=n; ++i){
			int j = s - i, cur[3][3];
			if(!j) break;

			for(int a=0; a<3; ++a)
				cur[a][0] = cur[a][1] = cur[a][2] = 0;

			for(int a=0; a<3; ++a){
				for(int b=0; b<3; ++b){
					for(int c=0; c<3; ++c){
						if(a == 1 && max(b, c) > a) continue;
						if(a == 1 && !up(i, j)) continue;
						if(a == 2 && !left(i, j)) continue;
						cur[a][b] = max(cur[a][b], bool(a) + dp[b][c]);
					}
				}
			}
			swap(dp, cur);
		}		
		for(int a=0; a<3; ++a)
			for(int b=0; b<3; ++b)
				dp[0][0] = max(dp[0][0], dp[a][b]);
		for(int a=0; a<3; ++a)
			for(int b=0; b<3; ++b)
				dp[a][b] = dp[0][0];
	}
	cout << dp[0][0];
}

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