#include <bits/stdc++.h>
#define maxn 3005
using namespace std;
int n,m;
char a[maxn][maxn];
int r[maxn][maxn];
int d[maxn][maxn];
int uk=0;
vector<int>adj[maxn*maxn];
int dp[maxn*maxn][2];
bool bio[maxn*maxn];
void dfs(int v)
{
dp[v][0]=0;
dp[v][1]=1;
bio[v]=true;
for(auto x:adj[v])
{
if(bio[v])continue;
dfs(x);
dp[v][0]+=max(dp[x][0],dp[x][1]);
dp[v][1]+=dp[x][0];
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n>>m;
for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>a[i][j];
for(int i=0;i<n;i++)for(int j=0;j<m;j++)
{
if(j+2<m && a[i][j]=='R' && a[i][j+1]=='G' && a[i][j+2]=='W')
{
r[i][j]=uk;
uk++;
}
else r[i][j]=-1;
if(i+2<n && a[i][j]=='R' && a[i+1][j]=='G' && a[i+2][j]=='W')
{
d[i][j]=uk;
uk++;
}
else d[i][j]=-1;
}
/*for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)cout<<d[i][j]<<","<<r[i][j]<<" ";
cout<<endl;
}*/
for(int i=0;i<n;i++)for(int j=0;j<m;j++)
{
if(d[i][j]!=-1)
{
if(r[i][j]!=-1)adj[d[i][j]].push_back(r[i][j]);
if(j-1>=0 && r[i+1][j-1]!=-1)adj[d[i][j]].push_back(r[i+1][j-1]);
if(j-2>=0 && r[i+2][j-2]!=-2)adj[d[i][j]].push_back(r[i+2][j-2]);
}
if(r[i][j]!=-1)
{
if(d[i][j]!=-1)adj[r[i][j]].push_back(d[i][j]);
if(i-1>=0 && d[i-1][j+1]!=-1)adj[r[i][j]].push_back(d[i-1][j+1]);
if(i-2>=0 && d[i-2][j+2]!=-1)adj[r[i][j]].push_back(d[i-2][j+2]);
}
}
int sol=0;
for(int i=0;i<uk;i++)bio[i]=false;
for(int i=0;i<uk;i++)if(!bio[i])
{
dfs(i);
sol+=max(dp[i][0],dp[i][1]);
}
cout<<sol<<endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
186 ms |
212344 KB |
Output is correct |
2 |
Correct |
188 ms |
212492 KB |
Output is correct |
3 |
Correct |
186 ms |
212672 KB |
Output is correct |
4 |
Correct |
183 ms |
212672 KB |
Output is correct |
5 |
Correct |
185 ms |
212672 KB |
Output is correct |
6 |
Incorrect |
188 ms |
212688 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
186 ms |
212344 KB |
Output is correct |
2 |
Correct |
188 ms |
212492 KB |
Output is correct |
3 |
Correct |
186 ms |
212672 KB |
Output is correct |
4 |
Correct |
183 ms |
212672 KB |
Output is correct |
5 |
Correct |
185 ms |
212672 KB |
Output is correct |
6 |
Incorrect |
188 ms |
212688 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
186 ms |
212344 KB |
Output is correct |
2 |
Correct |
188 ms |
212492 KB |
Output is correct |
3 |
Correct |
186 ms |
212672 KB |
Output is correct |
4 |
Correct |
183 ms |
212672 KB |
Output is correct |
5 |
Correct |
185 ms |
212672 KB |
Output is correct |
6 |
Incorrect |
188 ms |
212688 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |