제출 #1196265

#제출 시각아이디문제언어결과실행 시간메모리
1196265NewtonabcDango Maker (JOI18_dango_maker)C++20
100 / 100
229 ms9300 KiB
#include<bits/stdc++.h> using namespace std; const int N=3e3+10; char t[N][N]; //dp[row][skewer direction] int n,m,dp[N][3]; bool val1(int a,int b){ if(a-1<1 || a+1>n) return false; if(t[a][b]=='G' && t[a-1][b]=='R' && t[a+1][b]=='W') return true; return false; } bool val2(int a,int b){ if(b-1<1 || b+1>m) return false; if(t[a][b-1]=='R' && t[a][b]=='G' && t[a][b+1]=='W') return true; return false; } int main(){ cin>>n >>m; for(int i=1;i<=n;i++){ string s; cin>>s; for(int j=0;j<m;j++){ t[i][j+1]=s[j]; } } int ans=0; for(int sum=2;sum<=n+m;sum++){ int mx=0; int st=max(sum-m,1),ed=min(sum-1,n); dp[st][0]=dp[st][1]=dp[st][2]=0; if(val1(st,sum-st)) dp[st][1]=1,mx=1; if(val2(st,sum-st)) dp[st][2]=1,mx=1; //cout<<st <<" " <<sum-st <<"\n"; for(int row=st+1;row<=ed;row++){ //row+col=sum int col=sum-row; //cout<<row <<" " <<col <<"\n"; dp[row][0]=max({dp[row-1][0],dp[row-1][1],dp[row-1][2]}); if(val1(row,col)){ dp[row][1]=max(dp[row-1][0]+1,dp[row-1][1]+1); } else dp[row][1]=0; if(val2(row,col)){ dp[row][2]=max(dp[row-1][0]+1,dp[row-1][2]+1); } else dp[row][2]=0; mx=max({dp[row][0],dp[row][1],dp[row][2]}); //if(mx==1) cout<<"how"; } ans+=mx; } cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...