oj.uz

Submission #208833

# Submission time Handle Problem Language Result Execution time Memory
208833 2020-03-12T09:30:54 Z Siberian Dango Maker (JOI18_dango_maker) C++14
0 / 100
 136 ms 213240 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
#define all(x) x.begin(), x.end()

template <typename T1, typename T2> inline void chkmin(T1 &x, const T2 & y) {if (x > y) x = y;}
template <typename T1, typename T2> inline void chkmax(T1 &x, const T2 & y) {if (x < y) x = y;}

const int MAXN = 3010;
char table[MAXN][MAXN];
vector<int> g[MAXN * MAXN];
int n, m;

void read() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> table[i][j];
		}
	}
}

bool check_right(int i, int j) {
	return j >= 0 && j + 2 < m && i >= 0 && i < n && table[i][j] == 'R' && table[i][j + 1] == 'G' && table[i][j + 2] == 'W';
}

bool check_down(int i, int j) {
	return j >= 0 && j < m && i >= 0 && i + 2 < n && table[i][j] == 'R' && table[i + 1][j] == 'G' && table[i + 2][j] == 'W';
}

int cnt;

void build() {
	cnt = 0;
	for (int i = 0; i + 2 < n; i++) {
		for (int j = 0; j < m; j++) {
			if (table[i][j] != 'R') continue;
			if (table[i + 1][j] != 'G' || table[i + 2][j] != 'W') continue;
			if(check_right(i + 1, j - 1)) {
				g[i * m + j].push_back((i + 1) * m + j - 1);
			}
			if (check_right(i + 2, j - 2)) {
				g[i * m + j].push_back((i + 2) * m + j - 2);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cnt += check_right(i, j);
			cnt += check_down(i, j);
		}
	}
}

int used[MAXN * MAXN];
int mt[MAXN * MAXN];

bool dfs(int v, int c) {
	if (used[v] == c) return false;
	used[v] = c;
	for (auto i : g[v]) {
		if (mt[i] == -1) {
			mt[i] = v;
			return true;
		}
	}

	for (auto i : g[v]) {
		if (dfs(mt[i], c)) {
			mt[i] = v;
			return true;
		}
	}
	return false;
} 

int ans;

void calc() {
	for (int i = 0; i < n * m; i++) {
		mt[i] = used[i] = -1;
	}
	int c = 0;
	for (int i = 0; i < n * m; i++) {
		dfs(i, c++);
	}
	ans = cnt;
	for (int i = 0; i < n * m; i++) {
		if (mt[i] != -1) {
			ans--;
		}
	}
}

void run() {
	build();
	calc();
}

void write() {
	cout << ans << endl;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	read();
	run();
	write();
	return 0;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 213112 KB Output is correct
2 Correct 127 ms 213112 KB Output is correct
3 Correct 131 ms 213112 KB Output is correct
4 Correct 127 ms 213112 KB Output is correct
5 Correct 128 ms 213112 KB Output is correct
6 Correct 136 ms 213240 KB Output is correct
7 Correct 129 ms 213112 KB Output is correct
8 Incorrect 129 ms 213112 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 213112 KB Output is correct
2 Correct 127 ms 213112 KB Output is correct
3 Correct 131 ms 213112 KB Output is correct
4 Correct 127 ms 213112 KB Output is correct
5 Correct 128 ms 213112 KB Output is correct
6 Correct 136 ms 213240 KB Output is correct
7 Correct 129 ms 213112 KB Output is correct
8 Incorrect 129 ms 213112 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 213112 KB Output is correct
2 Correct 127 ms 213112 KB Output is correct
3 Correct 131 ms 213112 KB Output is correct
4 Correct 127 ms 213112 KB Output is correct
5 Correct 128 ms 213112 KB Output is correct
6 Correct 136 ms 213240 KB Output is correct
7 Correct 129 ms 213112 KB Output is correct
8 Incorrect 129 ms 213112 KB Output isn't correct
9 Halted 0 ms 0 KB -