#include <iostream>
#include <queue>
#include <vector>
#define pii pair<int,int>
#define fst first
#define snd second
using namespace std;
int n,m,to=0,dp[3001][3]={};string mp[3001]={};
bool bt[3001][3001][2]={},actv[3001][2]={};
queue<pii> q;
bool ck(int y,int x,int dr)
{
if (y>=0 && y<n-(dr?2:0) && x>=0 && x<m-((!dr)?2:0))
{
return mp[y][x] == 'R' && mp[y+dr][x+(!dr)] == 'G' && mp[y+2*dr][x+2*(!dr)] == 'W';
}
else {return 0;}
}
int main()
{
cin>>n>>m;
for (int i=0;i<n;i++) {cin>>mp[i];}
for (int i=0;i<n;i++)
{
for (int j=0;j<m;j++)
{
if (ck(i,j,0) && !bt[i][j][0])
{
for (int i=0;i<=n;i++)
{
actv[i][0] = actv[i][1] = 0;
dp[i][0] = dp[i][1] = dp[i][2] = 0;
}
int to1 = 0,to2 = 0;
q.push({i,j});
while (!q.empty())
{
pii dt = q.front();q.pop();
for (int i=0;i<3;i++)
{
if (!bt[dt.fst][dt.snd][0])
{
bt[dt.fst][dt.snd][0] = 1;
actv[dt.fst][0] = 1;
//cout<<dt.fst<<","<<dt.snd<<" 0 activated\n";
to1++;
for (int i=0;i<3;i++)
{
if (ck(dt.fst-i,dt.snd+i,1))
{
if (!bt[dt.fst-i][dt.snd+i][1])
{
to2 ++;
bt[dt.fst-i][dt.snd+i][1] = 1;
//cout<<dt.fst-i<<","<<dt.snd+i<<" 1 activated\n";
actv[dt.fst-i][1] = 1;
for (int j=0;j<3;j++)
{
if (j==i) {continue;}
if (ck(dt.fst-i+j,dt.snd+i-j,0))
{
q.push({dt.fst-i+j,dt.snd+i-j});
}
}
}
}
}
}
}
}
for (int i=1;i<=n;i++)
{
dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
dp[i][1] = dp[i-1][2];
dp[i][2] = 0;
if (actv[i-1][1])
{
dp[i][2] = max(dp[i][0],dp[i][1]) + 1;
}
if (actv[i-1][0])
{
dp[i][0]++;
}
//cout<<i<<" 0 -> "<<dp[i][0]<<"\n";
//cout<<i<<" 1 -> "<<dp[i][1]<<"\n";
//cout<<i<<" 2 -> "<<dp[i][2]<<"\n";
}
to+=max(dp[n][0],max(dp[n][1],dp[n][2]));
}
}
}
for (int i=0;i<n;i++)
{
for (int j=0;j<m;j++)
{
if (ck(i,j,1) && !bt[i][j][1]) {to++;}
}
}
cout<<to<<"\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
504 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
504 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
504 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |