제출 #97964

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

dango_maker

#pragma comment(linker, "/stack:200000000")
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

const int N = 3005;

vector<int> g[N * N];
int st[N * N], dr[N * N];
bitset<N * N> f;

vector<string> mx;
int n, m, fp;

static int cod(int l, int c) {
	return 1 + l * m + c; }

static bool match(int u) {
	if (f[u])
		return false;
	f[u] = 1;

	for (auto v: g[u]) if (!dr[v]) {
		st[u] = v;
		dr[v] = u;
		return true; }

	for (auto v: g[u]) if (match(dr[v])) {
		st[u] = v;
		dr[v] = u;
		return true; }
	return false;}


int main() {
#ifdef HOME
	freopen("joi_dango.in", "r", stdin);
	freopen("joi_dango.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int add, ant;

	cin >> n >> m;
	mx.resize(n);
	for (auto &line: mx)
		cin >> line;

	ant = 0;
	for (int i = 0; i < n; ++i)
	for (int j = 0; j < m; ++j) if (mx[i][j] == 'R') {
		bool hor = j + 2 < m ? (mx[i][j + 1] == 'G' && mx[i][j + 2] == 'W') : 0;
		bool ver = i + 2 < n ? (mx[i + 1][j] == 'G' && mx[i + 2][j] == 'W') : 0;

		ant+= int(hor) + int(ver);
		if (hor && ver)
			g[cod(i, j)].push_back(cod(i, j)); }

	for (int i = 2; i < n; ++i)
	for (int j = 2; j < m; ++j) if (mx[i][j] == 'W') {
		bool hor = mx[i][j - 2] == 'R' && mx[i][j - 1] == 'G';
		bool ver = mx[i - 2][j] == 'R' && mx[i - 1][j] == 'G';
		if (hor && ver)
			g[cod(i - 2, j)].push_back(cod(i, j - 2)); }
	
	

	for (int i = 1; i < n - 1; ++i)
	for (int j = 1; j < m - 1; ++j) if (mx[i][j] == 'G') {
		if (mx[i - 1][j] == 'R' && mx[i + 1][j] == 'W')
		if (mx[i][j - 1] == 'R' && mx[i][j + 1] == 'W')
			g[cod(i - 1, j)].push_back(cod(i, j - 1)); }

	mx.clear();
	mx.shrink_to_fit();

	do {
		f = 0;
		add = 0;
		for (int i = n * m; i >= 1; --i)
			if (!st[i] && !f[i])
				add+= int(match(i));
		ant-= add; }
	while (add);

	cout << ant << endl;

//	cerr << (sizeof(g) + sizeof(st) + sizeof(dr) + sizeof(f)) / 1024 / 1024 << endl;

	return 0; }

컴파일 시 표준 에러 (stderr) 메시지

dango_maker.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")

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