Submission #86853

#	Time	Username	Problem	Language	Result	Execution time	Memory
86853		KCSC	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	534 ms	148824 KiB

dango_maker

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

const int DIM = 3109;
const int di[9] = {-2, -2, -2, -1, -1, -1, 0, 0, 0};
const int dj[9] = {0, 1, 2, 0, 1, 2, 0, 1, 2};

char str[DIM][DIM];
pair<short, short> lef[DIM][DIM], rig[DIM][DIM];

bitset<DIM> mrk[DIM], val1[DIM], val2[DIM];

bool match(int x, int y, int &ans) {
	if (mrk[x][y]) {
		return false; }
	mrk[x][y] = true;
	for (int d = 0; d < 9; ++d) {
		int xx = x + di[d], yy = y + dj[d];
		if (xx >= 1 and val2[xx][yy] and rig[xx][yy].first == 0) {
			lef[x][y] = make_pair(xx, yy); 
			rig[xx][yy] = make_pair(x, y); 
			--ans; return true; } }
	for (int d = 0; d < 9; ++d) {
		int xx = x + di[d], yy = y + dj[d];
		if (xx >= 1 and val2[xx][yy] and match(rig[xx][yy].first, rig[xx][yy].second, ans)) {
			lef[x][y] = make_pair(xx, yy); 
			rig[xx][yy] = make_pair(x, y);
			return true; } } 
	return false; }

int main(void) {
#ifdef HOME
	freopen("dango.in", "r", stdin);
	freopen("dango.out", "w", stdout);
#endif
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		cin >> (str[i] + 1); }
	int ans = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (j + 2 <= m and str[i][j] == 'R' and str[i][j + 1] == 'G' and str[i][j + 2] == 'W') {
				val1[i][j] = true; ++ans; }
			if (i + 2 <= n and str[i][j] == 'R' and str[i + 1][j] == 'G' and str[i + 2][j] == 'W') {
				val2[i][j] = true; ++ans; } } }
	bool ok; do {
		ok = false;
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= m; ++j) {
				if (val1[i][j] and lef[i][j].first == 0 and match(i, j, ans)) {
					ok = true; } } }
	} while (ok);
	cout << ans;
	return 0; }

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