#include "bits/stdc++.h"
using namespace std;
using ll = long long;
// RGW
int n, m;
string s[3005];
int a[3005][3005], b[3005][3005];
vector<int> va[3000005];
int ma[3000005], mb[3000005];
bool visitb[3000005];
int cnt, cnt2;
stack<int> clrS;
bool dfs(int cur) {
for (int nxt : va[cur]) {
if (!visitb[nxt]) {
visitb[nxt] = true;
clrS.push(nxt);
if (mb[nxt] == -1 || dfs(mb[nxt])) {
ma[cur] = nxt;
mb[nxt] = cur;
return true;
}
}
}
return false;
}
int bipartite_matching() {
memset(ma, -1, sizeof(ma));
memset(mb, -1, sizeof(mb));
int ret = 0;
for (int i = 1; i <= cnt; i++) {
while (!clrS.empty()) {
visitb[clrS.top()] = false;
clrS.pop();
}
if (dfs(i)) ++ret;
}
return ret;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> s[i];
}
cnt = cnt2 = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (s[i][j] != 'R') continue;
if (j + 2 < m) {
if (s[i][j + 1] == 'G' && s[i][j + 2] == 'W') {
++cnt;
a[i][j] = cnt;
a[i][j + 1] = cnt;
a[i][j + 2] = cnt;
}
}
if (i + 2 < n) {
if (s[i + 1][j] == 'G' && s[i + 2][j] == 'W') {
++cnt2;
b[i][j]= cnt2;
b[i + 1][j]= cnt2;
b[i + 2][j]= cnt2;
}
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] != 0 && b[i][j] != 0) {
va[a[i][j]].push_back(b[i][j]);
}
}
}
cout << cnt + cnt2 - bipartite_matching() << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
94336 KB |
Output is correct |
2 |
Correct |
40 ms |
94236 KB |
Output is correct |
3 |
Correct |
40 ms |
94272 KB |
Output is correct |
4 |
Correct |
43 ms |
94280 KB |
Output is correct |
5 |
Correct |
44 ms |
94272 KB |
Output is correct |
6 |
Correct |
42 ms |
94300 KB |
Output is correct |
7 |
Correct |
44 ms |
94340 KB |
Output is correct |
8 |
Correct |
45 ms |
94260 KB |
Output is correct |
9 |
Correct |
45 ms |
94284 KB |
Output is correct |
10 |
Correct |
44 ms |
94316 KB |
Output is correct |
11 |
Correct |
44 ms |
94284 KB |
Output is correct |
12 |
Correct |
41 ms |
94276 KB |
Output is correct |
13 |
Correct |
43 ms |
94352 KB |
Output is correct |
14 |
Correct |
48 ms |
94308 KB |
Output is correct |
15 |
Correct |
46 ms |
94288 KB |
Output is correct |
16 |
Correct |
42 ms |
94244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
94336 KB |
Output is correct |
2 |
Correct |
40 ms |
94236 KB |
Output is correct |
3 |
Correct |
40 ms |
94272 KB |
Output is correct |
4 |
Correct |
43 ms |
94280 KB |
Output is correct |
5 |
Correct |
44 ms |
94272 KB |
Output is correct |
6 |
Correct |
42 ms |
94300 KB |
Output is correct |
7 |
Correct |
44 ms |
94340 KB |
Output is correct |
8 |
Correct |
45 ms |
94260 KB |
Output is correct |
9 |
Correct |
45 ms |
94284 KB |
Output is correct |
10 |
Correct |
44 ms |
94316 KB |
Output is correct |
11 |
Correct |
44 ms |
94284 KB |
Output is correct |
12 |
Correct |
41 ms |
94276 KB |
Output is correct |
13 |
Correct |
43 ms |
94352 KB |
Output is correct |
14 |
Correct |
48 ms |
94308 KB |
Output is correct |
15 |
Correct |
46 ms |
94288 KB |
Output is correct |
16 |
Correct |
42 ms |
94244 KB |
Output is correct |
17 |
Correct |
43 ms |
94256 KB |
Output is correct |
18 |
Correct |
41 ms |
94284 KB |
Output is correct |
19 |
Correct |
43 ms |
94360 KB |
Output is correct |
20 |
Correct |
45 ms |
94412 KB |
Output is correct |
21 |
Correct |
43 ms |
94412 KB |
Output is correct |
22 |
Correct |
42 ms |
94312 KB |
Output is correct |
23 |
Correct |
44 ms |
94420 KB |
Output is correct |
24 |
Correct |
43 ms |
94304 KB |
Output is correct |
25 |
Correct |
42 ms |
94256 KB |
Output is correct |
26 |
Correct |
42 ms |
94320 KB |
Output is correct |
27 |
Correct |
42 ms |
94412 KB |
Output is correct |
28 |
Correct |
43 ms |
94356 KB |
Output is correct |
29 |
Correct |
49 ms |
94324 KB |
Output is correct |
30 |
Correct |
41 ms |
94320 KB |
Output is correct |
31 |
Correct |
41 ms |
94292 KB |
Output is correct |
32 |
Correct |
42 ms |
94284 KB |
Output is correct |
33 |
Correct |
42 ms |
94404 KB |
Output is correct |
34 |
Correct |
42 ms |
94376 KB |
Output is correct |
35 |
Correct |
46 ms |
94428 KB |
Output is correct |
36 |
Correct |
43 ms |
94304 KB |
Output is correct |
37 |
Correct |
43 ms |
94368 KB |
Output is correct |
38 |
Correct |
44 ms |
94356 KB |
Output is correct |
39 |
Correct |
43 ms |
94408 KB |
Output is correct |
40 |
Correct |
41 ms |
94408 KB |
Output is correct |
41 |
Correct |
42 ms |
94420 KB |
Output is correct |
42 |
Correct |
43 ms |
94392 KB |
Output is correct |
43 |
Correct |
47 ms |
94340 KB |
Output is correct |
44 |
Correct |
50 ms |
94412 KB |
Output is correct |
45 |
Correct |
42 ms |
94420 KB |
Output is correct |
46 |
Correct |
45 ms |
94340 KB |
Output is correct |
47 |
Correct |
43 ms |
94548 KB |
Output is correct |
48 |
Correct |
42 ms |
94352 KB |
Output is correct |
49 |
Correct |
41 ms |
94412 KB |
Output is correct |
50 |
Correct |
43 ms |
94416 KB |
Output is correct |
51 |
Correct |
47 ms |
94312 KB |
Output is correct |
52 |
Correct |
43 ms |
94324 KB |
Output is correct |
53 |
Correct |
45 ms |
94420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
94336 KB |
Output is correct |
2 |
Correct |
40 ms |
94236 KB |
Output is correct |
3 |
Correct |
40 ms |
94272 KB |
Output is correct |
4 |
Correct |
43 ms |
94280 KB |
Output is correct |
5 |
Correct |
44 ms |
94272 KB |
Output is correct |
6 |
Correct |
42 ms |
94300 KB |
Output is correct |
7 |
Correct |
44 ms |
94340 KB |
Output is correct |
8 |
Correct |
45 ms |
94260 KB |
Output is correct |
9 |
Correct |
45 ms |
94284 KB |
Output is correct |
10 |
Correct |
44 ms |
94316 KB |
Output is correct |
11 |
Correct |
44 ms |
94284 KB |
Output is correct |
12 |
Correct |
41 ms |
94276 KB |
Output is correct |
13 |
Correct |
43 ms |
94352 KB |
Output is correct |
14 |
Correct |
48 ms |
94308 KB |
Output is correct |
15 |
Correct |
46 ms |
94288 KB |
Output is correct |
16 |
Correct |
42 ms |
94244 KB |
Output is correct |
17 |
Correct |
43 ms |
94256 KB |
Output is correct |
18 |
Correct |
41 ms |
94284 KB |
Output is correct |
19 |
Correct |
43 ms |
94360 KB |
Output is correct |
20 |
Correct |
45 ms |
94412 KB |
Output is correct |
21 |
Correct |
43 ms |
94412 KB |
Output is correct |
22 |
Correct |
42 ms |
94312 KB |
Output is correct |
23 |
Correct |
44 ms |
94420 KB |
Output is correct |
24 |
Correct |
43 ms |
94304 KB |
Output is correct |
25 |
Correct |
42 ms |
94256 KB |
Output is correct |
26 |
Correct |
42 ms |
94320 KB |
Output is correct |
27 |
Correct |
42 ms |
94412 KB |
Output is correct |
28 |
Correct |
43 ms |
94356 KB |
Output is correct |
29 |
Correct |
49 ms |
94324 KB |
Output is correct |
30 |
Correct |
41 ms |
94320 KB |
Output is correct |
31 |
Correct |
41 ms |
94292 KB |
Output is correct |
32 |
Correct |
42 ms |
94284 KB |
Output is correct |
33 |
Correct |
42 ms |
94404 KB |
Output is correct |
34 |
Correct |
42 ms |
94376 KB |
Output is correct |
35 |
Correct |
46 ms |
94428 KB |
Output is correct |
36 |
Correct |
43 ms |
94304 KB |
Output is correct |
37 |
Correct |
43 ms |
94368 KB |
Output is correct |
38 |
Correct |
44 ms |
94356 KB |
Output is correct |
39 |
Correct |
43 ms |
94408 KB |
Output is correct |
40 |
Correct |
41 ms |
94408 KB |
Output is correct |
41 |
Correct |
42 ms |
94420 KB |
Output is correct |
42 |
Correct |
43 ms |
94392 KB |
Output is correct |
43 |
Correct |
47 ms |
94340 KB |
Output is correct |
44 |
Correct |
50 ms |
94412 KB |
Output is correct |
45 |
Correct |
42 ms |
94420 KB |
Output is correct |
46 |
Correct |
45 ms |
94340 KB |
Output is correct |
47 |
Correct |
43 ms |
94548 KB |
Output is correct |
48 |
Correct |
42 ms |
94352 KB |
Output is correct |
49 |
Correct |
41 ms |
94412 KB |
Output is correct |
50 |
Correct |
43 ms |
94416 KB |
Output is correct |
51 |
Correct |
47 ms |
94312 KB |
Output is correct |
52 |
Correct |
43 ms |
94324 KB |
Output is correct |
53 |
Correct |
45 ms |
94420 KB |
Output is correct |
54 |
Correct |
45 ms |
94296 KB |
Output is correct |
55 |
Correct |
45 ms |
95692 KB |
Output is correct |
56 |
Correct |
49 ms |
94520 KB |
Output is correct |
57 |
Correct |
48 ms |
107084 KB |
Output is correct |
58 |
Correct |
60 ms |
112364 KB |
Output is correct |
59 |
Correct |
164 ms |
186936 KB |
Output is correct |
60 |
Correct |
169 ms |
186840 KB |
Output is correct |
61 |
Correct |
165 ms |
186912 KB |
Output is correct |
62 |
Correct |
40 ms |
94284 KB |
Output is correct |
63 |
Correct |
161 ms |
186120 KB |
Output is correct |
64 |
Runtime error |
443 ms |
262144 KB |
Execution killed with signal 9 |
65 |
Halted |
0 ms |
0 KB |
- |