제출 #86849

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
86849		KCSC	Dango Maker (JOI18_dango_maker)	C++14	33 / 100	548 ms	263168 KiB

dango_maker

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

const int DIM = 3005;
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];
int val1[DIM][DIM], val2[DIM][DIM]; bitset<DIM * DIM> mrk;

vector<int> edg[DIM * DIM]; int lef[DIM * DIM], rig[DIM * DIM];

bool match(int x, int &ans) {
	if (mrk[x]) {
		return false; }
	mrk[x] = true;
	for (int y : edg[x]) { if (!rig[y]) {
		lef[x] = y; rig[y] = x; --ans; return true; } }
	for (int y : edg[x]) { if (match(rig[y], ans)) {
		lef[x] = y; rig[y] = x; 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 nr1 = 0, nr2 = 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] = ++nr1; }
			if (i + 2 <= n and str[i][j] == 'R' and str[i + 1][j] == 'G' and str[i + 2][j] == 'W') {
				val2[i][j] = ++nr2; } } }
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (!val1[i][j]) {
				continue; }
			for (int d = 0; d < 9; ++d) {
				int ii = i + di[d], jj = j + dj[d];
				if (ii >= 1 and val2[ii][jj]) {
					edg[val1[i][j]].push_back(val2[ii][jj]); } } } }
	bool ok; int ans = nr1 + nr2; do {
		ok = false; mrk.reset();
		for (int i = 1; i <= nr1; ++i) {
			if (!lef[i] and match(i, ans)) {
				ok = true; } }
	} while (ok);
	cout << ans;
	return 0; }

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