#include <bits/stdc++.h>
using namespace std;
const int DIM = 3009;
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; }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
194 ms |
214136 KB |
Output is correct |
| 2 |
Correct |
197 ms |
214144 KB |
Output is correct |
| 3 |
Correct |
193 ms |
214184 KB |
Output is correct |
| 4 |
Correct |
192 ms |
214208 KB |
Output is correct |
| 5 |
Correct |
193 ms |
214400 KB |
Output is correct |
| 6 |
Correct |
191 ms |
214400 KB |
Output is correct |
| 7 |
Correct |
191 ms |
214400 KB |
Output is correct |
| 8 |
Correct |
190 ms |
214456 KB |
Output is correct |
| 9 |
Correct |
194 ms |
214456 KB |
Output is correct |
| 10 |
Correct |
186 ms |
214456 KB |
Output is correct |
| 11 |
Correct |
207 ms |
214456 KB |
Output is correct |
| 12 |
Correct |
214 ms |
214548 KB |
Output is correct |
| 13 |
Correct |
193 ms |
214548 KB |
Output is correct |
| 14 |
Correct |
190 ms |
214548 KB |
Output is correct |
| 15 |
Correct |
198 ms |
214564 KB |
Output is correct |
| 16 |
Correct |
211 ms |
214564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
194 ms |
214136 KB |
Output is correct |
| 2 |
Correct |
197 ms |
214144 KB |
Output is correct |
| 3 |
Correct |
193 ms |
214184 KB |
Output is correct |
| 4 |
Correct |
192 ms |
214208 KB |
Output is correct |
| 5 |
Correct |
193 ms |
214400 KB |
Output is correct |
| 6 |
Correct |
191 ms |
214400 KB |
Output is correct |
| 7 |
Correct |
191 ms |
214400 KB |
Output is correct |
| 8 |
Correct |
190 ms |
214456 KB |
Output is correct |
| 9 |
Correct |
194 ms |
214456 KB |
Output is correct |
| 10 |
Correct |
186 ms |
214456 KB |
Output is correct |
| 11 |
Correct |
207 ms |
214456 KB |
Output is correct |
| 12 |
Correct |
214 ms |
214548 KB |
Output is correct |
| 13 |
Correct |
193 ms |
214548 KB |
Output is correct |
| 14 |
Correct |
190 ms |
214548 KB |
Output is correct |
| 15 |
Correct |
198 ms |
214564 KB |
Output is correct |
| 16 |
Correct |
211 ms |
214564 KB |
Output is correct |
| 17 |
Correct |
193 ms |
214564 KB |
Output is correct |
| 18 |
Correct |
192 ms |
214564 KB |
Output is correct |
| 19 |
Correct |
194 ms |
214564 KB |
Output is correct |
| 20 |
Correct |
193 ms |
214564 KB |
Output is correct |
| 21 |
Correct |
191 ms |
214652 KB |
Output is correct |
| 22 |
Correct |
192 ms |
214652 KB |
Output is correct |
| 23 |
Correct |
188 ms |
214652 KB |
Output is correct |
| 24 |
Correct |
194 ms |
214652 KB |
Output is correct |
| 25 |
Correct |
184 ms |
214652 KB |
Output is correct |
| 26 |
Correct |
196 ms |
214652 KB |
Output is correct |
| 27 |
Correct |
195 ms |
214652 KB |
Output is correct |
| 28 |
Correct |
196 ms |
214652 KB |
Output is correct |
| 29 |
Correct |
193 ms |
214652 KB |
Output is correct |
| 30 |
Correct |
194 ms |
214652 KB |
Output is correct |
| 31 |
Correct |
195 ms |
214652 KB |
Output is correct |
| 32 |
Correct |
196 ms |
214652 KB |
Output is correct |
| 33 |
Correct |
191 ms |
214652 KB |
Output is correct |
| 34 |
Correct |
185 ms |
214704 KB |
Output is correct |
| 35 |
Correct |
194 ms |
214704 KB |
Output is correct |
| 36 |
Correct |
197 ms |
214704 KB |
Output is correct |
| 37 |
Correct |
197 ms |
214704 KB |
Output is correct |
| 38 |
Correct |
199 ms |
214712 KB |
Output is correct |
| 39 |
Correct |
195 ms |
214712 KB |
Output is correct |
| 40 |
Correct |
217 ms |
214712 KB |
Output is correct |
| 41 |
Correct |
188 ms |
214800 KB |
Output is correct |
| 42 |
Correct |
202 ms |
214800 KB |
Output is correct |
| 43 |
Correct |
190 ms |
214800 KB |
Output is correct |
| 44 |
Correct |
190 ms |
214800 KB |
Output is correct |
| 45 |
Correct |
187 ms |
214800 KB |
Output is correct |
| 46 |
Correct |
188 ms |
214800 KB |
Output is correct |
| 47 |
Correct |
192 ms |
214800 KB |
Output is correct |
| 48 |
Correct |
189 ms |
214800 KB |
Output is correct |
| 49 |
Correct |
197 ms |
214800 KB |
Output is correct |
| 50 |
Correct |
181 ms |
214800 KB |
Output is correct |
| 51 |
Correct |
189 ms |
214800 KB |
Output is correct |
| 52 |
Correct |
200 ms |
214800 KB |
Output is correct |
| 53 |
Correct |
194 ms |
214800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
194 ms |
214136 KB |
Output is correct |
| 2 |
Correct |
197 ms |
214144 KB |
Output is correct |
| 3 |
Correct |
193 ms |
214184 KB |
Output is correct |
| 4 |
Correct |
192 ms |
214208 KB |
Output is correct |
| 5 |
Correct |
193 ms |
214400 KB |
Output is correct |
| 6 |
Correct |
191 ms |
214400 KB |
Output is correct |
| 7 |
Correct |
191 ms |
214400 KB |
Output is correct |
| 8 |
Correct |
190 ms |
214456 KB |
Output is correct |
| 9 |
Correct |
194 ms |
214456 KB |
Output is correct |
| 10 |
Correct |
186 ms |
214456 KB |
Output is correct |
| 11 |
Correct |
207 ms |
214456 KB |
Output is correct |
| 12 |
Correct |
214 ms |
214548 KB |
Output is correct |
| 13 |
Correct |
193 ms |
214548 KB |
Output is correct |
| 14 |
Correct |
190 ms |
214548 KB |
Output is correct |
| 15 |
Correct |
198 ms |
214564 KB |
Output is correct |
| 16 |
Correct |
211 ms |
214564 KB |
Output is correct |
| 17 |
Correct |
193 ms |
214564 KB |
Output is correct |
| 18 |
Correct |
192 ms |
214564 KB |
Output is correct |
| 19 |
Correct |
194 ms |
214564 KB |
Output is correct |
| 20 |
Correct |
193 ms |
214564 KB |
Output is correct |
| 21 |
Correct |
191 ms |
214652 KB |
Output is correct |
| 22 |
Correct |
192 ms |
214652 KB |
Output is correct |
| 23 |
Correct |
188 ms |
214652 KB |
Output is correct |
| 24 |
Correct |
194 ms |
214652 KB |
Output is correct |
| 25 |
Correct |
184 ms |
214652 KB |
Output is correct |
| 26 |
Correct |
196 ms |
214652 KB |
Output is correct |
| 27 |
Correct |
195 ms |
214652 KB |
Output is correct |
| 28 |
Correct |
196 ms |
214652 KB |
Output is correct |
| 29 |
Correct |
193 ms |
214652 KB |
Output is correct |
| 30 |
Correct |
194 ms |
214652 KB |
Output is correct |
| 31 |
Correct |
195 ms |
214652 KB |
Output is correct |
| 32 |
Correct |
196 ms |
214652 KB |
Output is correct |
| 33 |
Correct |
191 ms |
214652 KB |
Output is correct |
| 34 |
Correct |
185 ms |
214704 KB |
Output is correct |
| 35 |
Correct |
194 ms |
214704 KB |
Output is correct |
| 36 |
Correct |
197 ms |
214704 KB |
Output is correct |
| 37 |
Correct |
197 ms |
214704 KB |
Output is correct |
| 38 |
Correct |
199 ms |
214712 KB |
Output is correct |
| 39 |
Correct |
195 ms |
214712 KB |
Output is correct |
| 40 |
Correct |
217 ms |
214712 KB |
Output is correct |
| 41 |
Correct |
188 ms |
214800 KB |
Output is correct |
| 42 |
Correct |
202 ms |
214800 KB |
Output is correct |
| 43 |
Correct |
190 ms |
214800 KB |
Output is correct |
| 44 |
Correct |
190 ms |
214800 KB |
Output is correct |
| 45 |
Correct |
187 ms |
214800 KB |
Output is correct |
| 46 |
Correct |
188 ms |
214800 KB |
Output is correct |
| 47 |
Correct |
192 ms |
214800 KB |
Output is correct |
| 48 |
Correct |
189 ms |
214800 KB |
Output is correct |
| 49 |
Correct |
197 ms |
214800 KB |
Output is correct |
| 50 |
Correct |
181 ms |
214800 KB |
Output is correct |
| 51 |
Correct |
189 ms |
214800 KB |
Output is correct |
| 52 |
Correct |
200 ms |
214800 KB |
Output is correct |
| 53 |
Correct |
194 ms |
214800 KB |
Output is correct |
| 54 |
Correct |
185 ms |
214800 KB |
Output is correct |
| 55 |
Correct |
205 ms |
223876 KB |
Output is correct |
| 56 |
Correct |
195 ms |
223876 KB |
Output is correct |
| 57 |
Correct |
213 ms |
230488 KB |
Output is correct |
| 58 |
Correct |
273 ms |
234724 KB |
Output is correct |
| 59 |
Runtime error |
634 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 60 |
Halted |
0 ms |
0 KB |
- |
