//By Don4ick
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
#define forn(i, n) for (int i = 1; i <= n; i++)
#define pb push_back
#define all(x) x.begin(), x.end()
#define y1 qwer1234
const double PI = acos(-1.0);
const int DIR = 4;
const int X[] = {1, 0, -1, 0};
const int Y[] = {0, 1, 0, -1};
const int N = 3005;
const int M = N * N * 2;
using namespace std;
int n, m, was[M], cnt0, cnt1;
vector < int > g[M];
string s[N];
void addEdge(int x1, int y1, int x2, int y2)
{
int v = x1 * m + y1, u = x2 * m + y2 + n * m;
g[v].pb(u), g[u].pb(v);
}
void dfs(int v)
{
if (was[v] == 0)
cnt0++;
else
cnt1++;
for (auto to : g[v])
{
if (was[to] != -1)
continue;
was[to] = was[v] ^ 1;
dfs(to);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
//~read
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> s[i];
}
//~build_graph
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m - 2; j++)
{
if (s[i][j] == 'R' && s[i][j + 1] == 'G' && s[i][j + 2] == 'W')
{
if (i < n - 2 && s[i + 1][j] == 'G' && s[i + 2][j] == 'W')
addEdge(i, j, i, j);
if (i < n - 1 && i > 0 && s[i - 1][j + 1] == 'R' && s[i + 1][j + 1] == 'W')
addEdge(i, j, i - 1, j + 1);
if (i > 1 && s[i - 2][j + 2] == 'R' && s[i - 1][j + 2] == 'G')
addEdge(i, j, i - 2, j + 2);
}
}
}
//~solve
memset(was, -1, sizeof(was));
int ans = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m - 2; j++)
{
int v = i * m + j;
if (s[i][j] == 'R' && s[i][j + 1] == 'G' && s[i][j + 2] == 'W' && was[v] == -1)
{
cnt0 = cnt1 = was[v] = 0;
dfs(v);
ans += max(cnt1, cnt0);
}
}
}
for (int i = 0; i < n - 2; i++)
{
for (int j = 0; j < m; j++)
{
int v = i * m + j + n * m;
if (s[i][j] == 'R' && s[i + 1][j] == 'G' && s[i + 2][j] == 'W' && was[v] == -1)
{
cnt0 = cnt1 = was[v] = 0;
dfs(v);
ans += max(cnt1, cnt0);
}
}
}
cout << ans << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1681 ms |
263168 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1681 ms |
263168 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1681 ms |
263168 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
