#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
const ll MAXN = 3E3+16;
char mat[MAXN][MAXN];
vector <pair <int, int> > th[2*MAXN];
ll dpBlue[MAXN];
ll dpRed[MAXN];
bool vBlue[MAXN];
bool vRed[MAXN];
int main () {
cin.tie(nullptr) -> sync_with_stdio(false);
ll n, m;
cin >> n >> m;
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < m; j++) {
cin >> mat[i][j];
if (mat[i][j] == 'R') mat[i][j] = '1';
if (mat[i][j] == 'G') mat[i][j] = '2';
if (mat[i][j] == 'W') mat[i][j] = '3';
th[i+j].push_back({ i, j });
}
}
auto isBlue = [&](ll i, ll j) {
if (0 <= i && i < n)
if (0 <= j && j+2 < m)
return mat[i][j] == '1' && mat[i][j+1] == '2' && mat[i][j+2] == '3';
return false;
};
auto isRed = [&](ll i, ll j) {
if (0 <= i && i+2 < n)
if (0 <= j && j < m)
return mat[i][j] == '1' && mat[i+1][j] == '2' && mat[i+2][j] == '3';
return false;
};
ll ans = 0;
for (ll sum = 0; sum <= n+m; sum++) {
if (!th[sum].size()) continue;
int off = 1E9;
for (auto [i, j] : th[sum]) off = min(off, j);
ll sz = th[sum].size()+6;
memset(dpBlue, 0, sizeof(ll)*sz);
memset(dpRed, 0, sizeof(ll)*sz);
memset(vBlue, 0, sizeof(bool)*sz);
memset(vRed, 0, sizeof(bool)*sz);
for (auto [i, j] : th[sum]) {
if (isBlue(i, j)) vBlue[j-off+3] = true;
if (isRed(i, j)) vRed[j-off+1] = true;
}
for (ll i = 1; i < sz; i++) {
dpBlue[i] = dpBlue[i-1];
dpRed[i] = dpRed[i-1];
if (vBlue[i]) dpBlue[i] = max({ dpBlue[i-1], dpRed[i-3] })+1;
if (vRed[i]) dpRed[i] = max({ dpRed[i-1], dpBlue[i-3] })+1;
}
ans += max(dpBlue[sz-1], dpRed[sz-1]);
}
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2408 KB |
Output is correct |
4 |
Correct |
1 ms |
2652 KB |
Output is correct |
5 |
Correct |
1 ms |
2652 KB |
Output is correct |
6 |
Correct |
1 ms |
2648 KB |
Output is correct |
7 |
Correct |
1 ms |
2652 KB |
Output is correct |
8 |
Correct |
1 ms |
2652 KB |
Output is correct |
9 |
Correct |
1 ms |
2648 KB |
Output is correct |
10 |
Correct |
1 ms |
2652 KB |
Output is correct |
11 |
Correct |
1 ms |
2648 KB |
Output is correct |
12 |
Correct |
1 ms |
2652 KB |
Output is correct |
13 |
Correct |
1 ms |
2652 KB |
Output is correct |
14 |
Correct |
1 ms |
2652 KB |
Output is correct |
15 |
Correct |
1 ms |
2652 KB |
Output is correct |
16 |
Correct |
1 ms |
2652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2408 KB |
Output is correct |
4 |
Correct |
1 ms |
2652 KB |
Output is correct |
5 |
Correct |
1 ms |
2652 KB |
Output is correct |
6 |
Correct |
1 ms |
2648 KB |
Output is correct |
7 |
Correct |
1 ms |
2652 KB |
Output is correct |
8 |
Correct |
1 ms |
2652 KB |
Output is correct |
9 |
Correct |
1 ms |
2648 KB |
Output is correct |
10 |
Correct |
1 ms |
2652 KB |
Output is correct |
11 |
Correct |
1 ms |
2648 KB |
Output is correct |
12 |
Correct |
1 ms |
2652 KB |
Output is correct |
13 |
Correct |
1 ms |
2652 KB |
Output is correct |
14 |
Correct |
1 ms |
2652 KB |
Output is correct |
15 |
Correct |
1 ms |
2652 KB |
Output is correct |
16 |
Correct |
1 ms |
2652 KB |
Output is correct |
17 |
Correct |
1 ms |
2652 KB |
Output is correct |
18 |
Correct |
0 ms |
2652 KB |
Output is correct |
19 |
Correct |
1 ms |
2652 KB |
Output is correct |
20 |
Correct |
1 ms |
2652 KB |
Output is correct |
21 |
Correct |
1 ms |
2652 KB |
Output is correct |
22 |
Incorrect |
1 ms |
2648 KB |
Output isn't correct |
23 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2408 KB |
Output is correct |
4 |
Correct |
1 ms |
2652 KB |
Output is correct |
5 |
Correct |
1 ms |
2652 KB |
Output is correct |
6 |
Correct |
1 ms |
2648 KB |
Output is correct |
7 |
Correct |
1 ms |
2652 KB |
Output is correct |
8 |
Correct |
1 ms |
2652 KB |
Output is correct |
9 |
Correct |
1 ms |
2648 KB |
Output is correct |
10 |
Correct |
1 ms |
2652 KB |
Output is correct |
11 |
Correct |
1 ms |
2648 KB |
Output is correct |
12 |
Correct |
1 ms |
2652 KB |
Output is correct |
13 |
Correct |
1 ms |
2652 KB |
Output is correct |
14 |
Correct |
1 ms |
2652 KB |
Output is correct |
15 |
Correct |
1 ms |
2652 KB |
Output is correct |
16 |
Correct |
1 ms |
2652 KB |
Output is correct |
17 |
Correct |
1 ms |
2652 KB |
Output is correct |
18 |
Correct |
0 ms |
2652 KB |
Output is correct |
19 |
Correct |
1 ms |
2652 KB |
Output is correct |
20 |
Correct |
1 ms |
2652 KB |
Output is correct |
21 |
Correct |
1 ms |
2652 KB |
Output is correct |
22 |
Incorrect |
1 ms |
2648 KB |
Output isn't correct |
23 |
Halted |
0 ms |
0 KB |
- |