#include <bits/stdc++.h>
#define maxn 3005
#define maxnode maxn*maxn/3
#define INF 1000000000
using namespace std;
int n,m;
char a[maxn][maxn];
int r[maxn][maxn];
int d[maxn][maxn];
int uk=0;
vector<int>adj[maxnode];
int dp[maxnode][2];
bool bio[maxnode];
int cyc=0;
int t[maxnode];
int lu[maxnode/4];
int ld[maxnode/4];
int ru[maxnode/4];
int rd[maxnode/4];
int dpcyc[maxnode/4][9];
//kolicnik gore
//ostatak dole
bool bcyc[maxnode/4];
bool proso(int v)
{
if(bio[v])return true;
if(t[v]!=-1 && bcyc[t[v]])return true;
return false;
}
void dfs(int v)
{
dp[v][0]=0;
dp[v][1]=1;
bio[v]=true;
if(t[v]!=-1)
{
int tt=t[v];
bcyc[tt]=true;
for(auto x:adj[ld[tt]])
{
if(proso(x))continue;
dfs(x);
for(int k=0;k<9;k++)
{
if(k%3!=1)dpcyc[tt][k]+=max(dp[x][0],dp[x][1]);
else dpcyc[tt][k]+=dp[x][0];
}
}
for(auto x:adj[lu[tt]])
{
if(proso(x))continue;
dfs(x);
for(int k=0;k<9;k++)
{
if(k/3!=1)dpcyc[tt][k]+=max(dp[x][0],dp[x][1]);
else dpcyc[tt][k]+=dp[x][0];
}
}
for(auto x:adj[rd[tt]])
{
if(proso(x))continue;
dfs(x);
for(int k=0;k<9;k++)
{
if(k%3!=2)dpcyc[tt][k]+=max(dp[x][0],dp[x][1]);
else dpcyc[tt][k]+=dp[x][0];
}
}
for(auto x:adj[ru[tt]])
{
if(proso(x))continue;
dfs(x);
for(int k=0;k<9;k++)
{
if(k/3!=2)dpcyc[tt][k]+=max(dp[x][0],dp[x][1]);
else dpcyc[tt][k]+=dp[x][0];
}
}
}
else{
for(auto x:adj[v])
{
if(proso(x))continue;
dfs(x);
if(t[x]!=-1)
{
int tt=t[x];
if(x==lu[tt])
{
int dod0=0;
int dod1=0;
for(int k=0;k<9;k++)
{
dod0=max(dod0,dpcyc[tt][k]);
if(k/3!=1)dod1=max(dod1,dpcyc[tt][k]);
}
dp[v][0]+=dod0;
dp[v][1]+=dod1;
}
if(x==ld[tt])
{
int dod0=0;
int dod1=0;
for(int k=0;k<9;k++)
{
dod0=max(dod0,dpcyc[tt][k]);
if(k%3!=1)dod1=max(dod1,dpcyc[tt][k]);
}
dp[v][0]+=dod0;
dp[v][1]+=dod1;
}
if(x==rd[tt])
{
int dod0=0;
int dod1=0;
for(int k=0;k<9;k++)
{
dod0=max(dod0,dpcyc[tt][k]);
if(k%3!=2)dod1=max(dod1,dpcyc[tt][k]);
}
dp[v][0]+=dod0;
dp[v][1]+=dod1;
}
if(x==ru[tt])
{
int dod0=0;
int dod1=0;
for(int k=0;k<9;k++)
{
dod0=max(dod0,dpcyc[tt][k]);
if(k/3!=2)dod1=max(dod1,dpcyc[tt][k]);
}
dp[v][0]+=dod0;
dp[v][1]+=dod1;
}
}
else
{
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<uk;i++)t[i]=-1;
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(i+2<n && j-2>=0 && r[i+1][j-1]!=-1 && r[i+2][j-2]!=-1 && d[i+1][j-1]!=-1)
{
int xx=d[i][j];
int yy=r[i+1][j-1];
int zz=r[i+2][j-2];
int tt=d[i+1][j-1];
int br=t[xx];
if(t[yy]!=-1)br=t[yy];
if(t[zz]!=-1)br=t[zz];
if(t[tt]!=-1)br=t[tt];
if(br==-1)
{
br=cyc;
cyc++;
lu[br]=xx;
ru[br]=yy;
for(int k=0;k<9;k++)
{
if(k%3==0 && k/3==0)dpcyc[br][k]=0;
else if(k%3==0 || k/3==0)dpcyc[br][k]=1;
else if(k/3==k%3)dpcyc[br][k]=-INF;
else dpcyc[br][k]=2;
}
}
else
{
int asd[9];
for(int k=0;k<9;k++)
{
if(k%3==0 || k/3==0)asd[k]=dpcyc[br][k]+1;
else
{
int maxx=0;
for(int kk=0;kk<9;kk++)if(kk%3!=k%3 && maxx<dpcyc[br][kk])maxx=dpcyc[br][kk];
asd[k]=maxx+1;
}
}
for(int k=0;k<9;k++)dpcyc[br][k]=asd[k];
}
t[xx]=t[yy]=t[zz]=t[tt]=br;
rd[br]=tt;
ld[br]=zz;
}
}
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]);
if(i+1<n && i-1>=0 && j+1<m && j-1>=0 && d[i-1][j+1]!=-1 && r[i+1][j-1]!=-1 && d[i][j]!=-1)
{
int xx=d[i-1][j+1];
int yy=r[i][j];
int zz=r[i+1][j-1];
int tt=d[i][j];
int br=t[xx];
if(t[yy]!=-1)br=t[yy];
if(t[zz]!=-1)br=t[zz];
if(t[tt]!=-1)br=t[tt];
if(br==-1)
{
br=cyc;
cyc++;
lu[br]=xx;
ru[br]=yy;
for(int k=0;k<9;k++)
{
if(k%3==0 && k/3==0)dpcyc[br][k]=0;
else if(k%3==0 || k/3==0)dpcyc[br][k]=1;
else if(k/3==k%3)dpcyc[br][k]=-INF;
else dpcyc[br][k]=2;
}
}
else
{
int asd[9];
for(int k=0;k<9;k++)
{
if(k%3==0 || k/3==0)asd[k]=dpcyc[br][k]+1;
else
{
int maxx=0;
for(int kk=0;kk<9;kk++)if(kk%3!=k%3 && maxx<dpcyc[br][kk])maxx=dpcyc[br][kk];
asd[k]=maxx+1;
}
}
for(int k=0;k<9;k++)dpcyc[br][k]=asd[k];
}
t[xx]=t[yy]=t[zz]=t[tt]=br;
rd[br]=tt;
ld[br]=zz;
}
}
}
int sol=0;
for(int i=0;i<uk;i++)bio[i]=false;
for(int i=0;i<cyc;i++)bcyc[i]=false;
for(int i=0;i<uk;i++)if(!proso(i))
{
dfs(i);
if(t[i]==-1)sol+=max(dp[i][0],dp[i][1]);
else{
int maxx=0;
for(int k=0;k<9;k++)if(maxx<dp[t[i]][k])maxx=dp[t[i]][k];
sol+=maxx;
}
}
cout<<sol<<endl;
return 0;
}
Compilation message
dango_maker.cpp: In function 'int main()':
dango_maker.cpp:318:51: warning: iteration 2 invokes undefined behavior [-Waggressive-loop-optimizations]
for(int k=0;k<9;k++)if(maxx<dp[t[i]][k])maxx=dp[t[i]][k];
~~~~~~~~~~^
dango_maker.cpp:318:26: note: within this loop
for(int k=0;k<9;k++)if(maxx<dp[t[i]][k])maxx=dp[t[i]][k];
~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
71032 KB |
Output is correct |
2 |
Correct |
65 ms |
71032 KB |
Output is correct |
3 |
Correct |
65 ms |
71072 KB |
Output is correct |
4 |
Correct |
64 ms |
71124 KB |
Output is correct |
5 |
Correct |
64 ms |
71252 KB |
Output is correct |
6 |
Correct |
64 ms |
71252 KB |
Output is correct |
7 |
Correct |
63 ms |
71384 KB |
Output is correct |
8 |
Correct |
64 ms |
71384 KB |
Output is correct |
9 |
Correct |
63 ms |
71384 KB |
Output is correct |
10 |
Correct |
64 ms |
71404 KB |
Output is correct |
11 |
Correct |
62 ms |
71404 KB |
Output is correct |
12 |
Correct |
68 ms |
71420 KB |
Output is correct |
13 |
Correct |
66 ms |
71420 KB |
Output is correct |
14 |
Correct |
79 ms |
71420 KB |
Output is correct |
15 |
Correct |
66 ms |
71420 KB |
Output is correct |
16 |
Correct |
64 ms |
71420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
71032 KB |
Output is correct |
2 |
Correct |
65 ms |
71032 KB |
Output is correct |
3 |
Correct |
65 ms |
71072 KB |
Output is correct |
4 |
Correct |
64 ms |
71124 KB |
Output is correct |
5 |
Correct |
64 ms |
71252 KB |
Output is correct |
6 |
Correct |
64 ms |
71252 KB |
Output is correct |
7 |
Correct |
63 ms |
71384 KB |
Output is correct |
8 |
Correct |
64 ms |
71384 KB |
Output is correct |
9 |
Correct |
63 ms |
71384 KB |
Output is correct |
10 |
Correct |
64 ms |
71404 KB |
Output is correct |
11 |
Correct |
62 ms |
71404 KB |
Output is correct |
12 |
Correct |
68 ms |
71420 KB |
Output is correct |
13 |
Correct |
66 ms |
71420 KB |
Output is correct |
14 |
Correct |
79 ms |
71420 KB |
Output is correct |
15 |
Correct |
66 ms |
71420 KB |
Output is correct |
16 |
Correct |
64 ms |
71420 KB |
Output is correct |
17 |
Correct |
66 ms |
71420 KB |
Output is correct |
18 |
Correct |
65 ms |
71420 KB |
Output is correct |
19 |
Correct |
65 ms |
71420 KB |
Output is correct |
20 |
Correct |
65 ms |
71420 KB |
Output is correct |
21 |
Correct |
64 ms |
71492 KB |
Output is correct |
22 |
Correct |
63 ms |
71492 KB |
Output is correct |
23 |
Correct |
67 ms |
71492 KB |
Output is correct |
24 |
Correct |
66 ms |
71492 KB |
Output is correct |
25 |
Correct |
63 ms |
71492 KB |
Output is correct |
26 |
Correct |
66 ms |
71492 KB |
Output is correct |
27 |
Incorrect |
63 ms |
71536 KB |
Output isn't correct |
28 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
71032 KB |
Output is correct |
2 |
Correct |
65 ms |
71032 KB |
Output is correct |
3 |
Correct |
65 ms |
71072 KB |
Output is correct |
4 |
Correct |
64 ms |
71124 KB |
Output is correct |
5 |
Correct |
64 ms |
71252 KB |
Output is correct |
6 |
Correct |
64 ms |
71252 KB |
Output is correct |
7 |
Correct |
63 ms |
71384 KB |
Output is correct |
8 |
Correct |
64 ms |
71384 KB |
Output is correct |
9 |
Correct |
63 ms |
71384 KB |
Output is correct |
10 |
Correct |
64 ms |
71404 KB |
Output is correct |
11 |
Correct |
62 ms |
71404 KB |
Output is correct |
12 |
Correct |
68 ms |
71420 KB |
Output is correct |
13 |
Correct |
66 ms |
71420 KB |
Output is correct |
14 |
Correct |
79 ms |
71420 KB |
Output is correct |
15 |
Correct |
66 ms |
71420 KB |
Output is correct |
16 |
Correct |
64 ms |
71420 KB |
Output is correct |
17 |
Correct |
66 ms |
71420 KB |
Output is correct |
18 |
Correct |
65 ms |
71420 KB |
Output is correct |
19 |
Correct |
65 ms |
71420 KB |
Output is correct |
20 |
Correct |
65 ms |
71420 KB |
Output is correct |
21 |
Correct |
64 ms |
71492 KB |
Output is correct |
22 |
Correct |
63 ms |
71492 KB |
Output is correct |
23 |
Correct |
67 ms |
71492 KB |
Output is correct |
24 |
Correct |
66 ms |
71492 KB |
Output is correct |
25 |
Correct |
63 ms |
71492 KB |
Output is correct |
26 |
Correct |
66 ms |
71492 KB |
Output is correct |
27 |
Incorrect |
63 ms |
71536 KB |
Output isn't correct |
28 |
Halted |
0 ms |
0 KB |
- |