#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int N = 3000;
string s[N+5];
int dp[N+5][3];
int main(){
ios_base::sync_with_stdio(false), cin.tie(0);
cout.precision(10);
cout << fixed;
int n, m;
cin >> n >> m;
for(int i=1; i<=m; i++) s[0] += ".";
for(int i=1; i<=n; i++){
string str;
cin >> str;
s[i] = "." + str;
s[i] += ".";
}
for(int i=1; i<=m; i++) s[n+1] += ".";
int res = 0;
dp[0][1] = dp[0][2] = -N;
for(int si=1; si<=n; si++){
int i = si, j = 1;
while(i > 0){
dp[j][0] = max(dp[j-1][0], max(dp[j-1][1], dp[j-1][2]));
if(s[i-1][j] == 'R' && s[i][j] == 'G' && s[i+1][j] == 'W') dp[j][1] = 1 + max(dp[j-1][0], dp[j-1][1]);
else dp[j][1] = -N;
if(s[i][j-1] == 'R' && s[i][j] == 'G' && s[i][j+1] == 'W') dp[j][2] = 1 + max(dp[j-1][0], dp[j-1][2]);
else dp[j][2] = -N;
i--;
j++;
}
res += max(dp[j-1][0], max(dp[j-1][1], dp[j-1][2]));
}
for(int sj=2; sj<=m; sj++){
int i = n, j = sj;
dp[sj-1][0] = 0;
dp[sj-1][1] = dp[sj-1][2] = -N;
while(j <= m){
dp[j][0] = max(dp[j-1][0], max(dp[j-1][1], dp[j-1][2]));
if(s[i-1][j] == 'R' && s[i][j] == 'G' && s[i+1][j] == 'W') dp[j][1] = 1 + max(dp[j-1][0], dp[j-1][1]);
else dp[j][1] = -N;
if(s[i][j-1] == 'R' && s[i][j] == 'G' && s[i][j+1] == 'W') dp[j][2] = 1 + max(dp[j-1][0], dp[j-1][2]);
else dp[j][2] = -N;
i--;
j++;
}
res += max(dp[j-1][0], max(dp[j-1][1], dp[j-1][2]));
}
cout << res << "\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
444 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
444 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
332 KB |
Output is correct |
17 |
Correct |
0 ms |
332 KB |
Output is correct |
18 |
Correct |
0 ms |
332 KB |
Output is correct |
19 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 11 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
444 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
332 KB |
Output is correct |
17 |
Correct |
0 ms |
332 KB |
Output is correct |
18 |
Correct |
0 ms |
332 KB |
Output is correct |
19 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 11 |
20 |
Halted |
0 ms |
0 KB |
- |