#include<bits/stdc++.h>
using namespace std;
const int N = (int)3e3+7;
const long long INF = (long long)1e18+7;
int n, m, ans;
bool b[N][N], c[N][N];
char a[N][N];
vector<pair<bool, bool> > v[2*N];
int dp[N][2];
int get(vector<pair<bool, bool> > &h) {
int t = (int)h.size();
for(int i = 0; i < t; ++i) {
dp[i][0]=dp[i][1]=0;
}
int res = 0;
for(int i = 3; i < t; ++i) {
if(h[i].first) {
dp[i][0]=max(dp[i][0], dp[i-1][0]);
dp[i][0]=max(dp[i][0], dp[i-1][1]);
dp[i][0]=max(dp[i][0], dp[i-2][0]);
dp[i][0]=max(dp[i][0], dp[i-2][1]);
dp[i][0]++;
}
if(h[i].second) {
dp[i][1]=max(dp[i][1], dp[i-1][1]);
dp[i][1]=max(dp[i][1], dp[i-2][1]);
dp[i][1]=max(dp[i][1], dp[i-3][0]);
dp[i][1]++;
}
res=max(res, dp[i][0]);
res=max(res, dp[i][1]);
}
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
cin >> a[i][j];
}
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(j+2<=m && a[i][j]=='R' && a[i][j+1]=='G' && a[i][j+2]=='W') {
b[i][j]=1;
}
if(i+2<=n && a[i][j]=='R' && a[i+1][j]=='G' && a[i+2][j]=='W') {
c[i][j]=1;
}
}
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
v[i+j].push_back({b[i][j], c[i][j]});
}
}
for(int i = 1; i <= n+m; ++i) {
v[i].push_back({0, 0});
v[i].push_back({0, 0});
v[i].push_back({0, 0});
}
for(int i = 1; i <= n+m; ++i) {
reverse(v[i].begin(), v[i].end());
ans += get(v[i]);
}
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
604 KB |
Output is correct |
2 |
Correct |
0 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
600 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
4700 KB |
Output is correct |
7 |
Correct |
1 ms |
4700 KB |
Output is correct |
8 |
Correct |
1 ms |
4700 KB |
Output is correct |
9 |
Correct |
1 ms |
4700 KB |
Output is correct |
10 |
Correct |
1 ms |
2652 KB |
Output is correct |
11 |
Correct |
1 ms |
4700 KB |
Output is correct |
12 |
Correct |
1 ms |
4700 KB |
Output is correct |
13 |
Correct |
1 ms |
4700 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 |
0 ms |
604 KB |
Output is correct |
2 |
Correct |
0 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
600 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
4700 KB |
Output is correct |
7 |
Correct |
1 ms |
4700 KB |
Output is correct |
8 |
Correct |
1 ms |
4700 KB |
Output is correct |
9 |
Correct |
1 ms |
4700 KB |
Output is correct |
10 |
Correct |
1 ms |
2652 KB |
Output is correct |
11 |
Correct |
1 ms |
4700 KB |
Output is correct |
12 |
Correct |
1 ms |
4700 KB |
Output is correct |
13 |
Correct |
1 ms |
4700 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 |
4700 KB |
Output is correct |
18 |
Correct |
1 ms |
4700 KB |
Output is correct |
19 |
Incorrect |
1 ms |
6748 KB |
Output isn't correct |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
604 KB |
Output is correct |
2 |
Correct |
0 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
600 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
4700 KB |
Output is correct |
7 |
Correct |
1 ms |
4700 KB |
Output is correct |
8 |
Correct |
1 ms |
4700 KB |
Output is correct |
9 |
Correct |
1 ms |
4700 KB |
Output is correct |
10 |
Correct |
1 ms |
2652 KB |
Output is correct |
11 |
Correct |
1 ms |
4700 KB |
Output is correct |
12 |
Correct |
1 ms |
4700 KB |
Output is correct |
13 |
Correct |
1 ms |
4700 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 |
4700 KB |
Output is correct |
18 |
Correct |
1 ms |
4700 KB |
Output is correct |
19 |
Incorrect |
1 ms |
6748 KB |
Output isn't correct |
20 |
Halted |
0 ms |
0 KB |
- |