Submission #679573

#	Time	Username	Problem	Language	Result	Execution time	Memory
679573		minhcool	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	1249 ms	18352 KiB

dango_maker

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e3 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

int n, m;

char c[N][N];

int dp[2 * N][3][3];

bool ck(int x, int y, int dir){
	if(dir == 2) return 0;
	if(!dir){
		if(y >= (m - 1)) return 0;
		return (c[x][y] == 'R' && c[x][y + 1] == 'G' && c[x][y + 2] == 'W');
	}
	else{
		if(x >= (n - 1)) return 0;
		return (c[x][y] == 'R' && c[x + 1][y] == 'G' && c[x + 2][y] == 'W');
	}
}

void process(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++) cin >> c[i][j];
	}
	int answer = 0;
	for(int i = 2; i <= (n + m); i++){
		int sta = max(i - m, 1LL), en = min(n, i - 1);
		for(int j = sta; j <= en; j++){
			for(int k = 0; k < 3; k++){
				for(int h = 0; h < 3; h++) dp[j][k][h] = -oo;
			}
		}
		dp[sta][2][0] = 0;
		dp[sta][0][0] = ck(sta, i - sta, 0);
		dp[sta][1][0] = ck(sta, i - sta, 1);
		for(int j = sta; j < en; j++){
			for(int k = 0; k <= 2; k++){
				for(int h = 0; h <= 2; h++){
					for(int nxt = 0; nxt <= 2; nxt++){
						if(nxt == 0){
							if(k == 1 || h == 1) continue;
						}
						dp[j + 1][nxt][k] = max(dp[j + 1][nxt][k], dp[j][k][h] + ck(j + 1, i - (j + 1), nxt));
					}
				}
			}
		}
		int temp = -1;
		for(int i = 0; i <= 2; i++){
			for(int j = 0; j <= 2; j++) temp = max(temp, dp[en][i][j]);
		}
		//cout << i << " " << temp << "\n";
		answer += temp;
	}
	cout << answer << "\n";
}

signed main(){
	ios_base::sync_with_stdio(0);
	int t = 1;
	//cin >> t;
	while(t--) process();
}

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