oj.uz

답안 #86851

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
86851 2018-11-27T20:30:15 Z KCSC Dango Maker (JOI18_dango_maker) C++14
0 / 100
 205 ms 263168 KB 
#include <bits/stdc++.h>
using namespace std;

const int DIM = 6009;
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]; 
int lef[DIM * DIM], rig[DIM * DIM];

bitset<DIM * DIM> mrk;
vector<int> edg[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; } } }
	assert(nr1 <= n * m and nr2 <= n * m);
	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 jj <= m 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
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 205 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 205 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 205 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -