// Papryko, daj lepsze zadanka
#include <bits/stdc++.h>
using namespace std;
int n, m, dp[6000], czy[3000][3000][2];
string dango[3000];
void triv() {
int odp = 0;
if (n < 3) {
for (int i = 0; i < n; i++)
for (int j = 2; j < m; j++)
if (dango[i][j-2] == 'R' && dango[i][j-1] == 'G' && dango[i][j] == 'W')
odp++;
}
else {
for (int j = 0; j < m; j++)
for (int i = 2; i < n; i++)
if (dango[i-2][j] == 'R' && dango[i-1][j] == 'G' && dango[i][j] == 'W')
odp++;
}
cout << odp << endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> dango[i];
if (min(n,m) < 3)
triv();
else {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (dango[i][j] == 'W') {
czy[i][j][0] = ((j > 1 && dango[i][j-2] == 'R' && dango[i][j-1] == 'G' && dango[i][j] == 'W') ? 1 : 0);
czy[i][j][1] = ((i > 1 && dango[i-2][j] == 'R' && dango[i-1][j] == 'G' && dango[i][j] == 'W') ? 1 : 0);
}
else
czy[i][j][0] = czy[i][j][1] = 0;
}
}
for (int i = 2; i < n+m; i++) {
int x = min(i,n-1), y = i-x, pom[n+m][2], k = 0;
pom[k][0] = czy[x][y][0], pom[k][1] = czy[x][y][1], k++;
while (x > 0) {
x--, y++,
pom[k][0] = czy[x][y][0] + max(pom[k-1][0],((k > 2) ? pom[k-3][1] : 0));
pom[k][1] = czy[x][y][1] + max(pom[k-1][0],pom[k-1][1]), k++;
}
dp[i] = dp[i-1] + max(pom[k-1][0],pom[k-1][1]);
}
cout << dp[n+m-1] << endl;
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |