Submission #64257

#	Time	Username	Problem	Language	Result	Execution time	Memory
64257		keko37	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	1746 ms	254756 KiB

dango_maker

#include<iostream>
#include<cstring>

using namespace std;

const int MAXN = 3005;

int n, m, a, b, sol;
char l[MAXN] [MAXN];
int dp[MAXN] [MAXN] [4];

bool ok (int x, int y, int d) {
	if (d == 0) {
		return l[x] [y] == 'R' && l[x+1] [y] == 'G' && l[x+2] [y] == 'W';
	} else {
		return l[x] [y] == 'R' && l[x] [y+1] == 'G' && l[x] [y+2] == 'W';
	}
}

int f (int x, int y, int mask) {
	if (l[x] [y] != 'R' || x < 0) return 0;
	if (dp[x] [y] [mask] != -1) return dp[x] [y] [mask];
	int res = 0;
	res = max(res, f(x-1, y+1, (2*mask)%4));
	res = max(res, f(x-2, y+2, 0));
	if (ok(x, y, 0) && mask == 0) {
		res = max(res, 1+f(x-1, y+1, 0));
		res = max(res, 1+f(x-2, y+2, 0));
	}
	if (ok(x, y, 1)) {
		res = max(res, 1+f(x-1, y+1, (mask*2 + 1)%4));
		res = max(res, 1+f(x-2, y+2, 2));
	}
	dp[x] [y] [mask] = res;
	return res;
}

int main () {
	memset(dp, -1, sizeof dp);
	cin >> n >> m;
	for (int i=0; i<n; i++) {
		for (int j=0; j<m; j++) {
			cin >> l[i] [j];
		}
	}
	for (int i=n-1; i>=0; i--) {
		for (int j=m-1; j>=0; j--) {
			if (dp[i] [j] [0] == -1) {
				sol += f(i, j, 0);
			}
		}
	}
	cout << sol;
	return 0;
}

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