Submission #1317264

#TimeUsernameProblemLanguageResultExecution timeMemory
1317264nambanana987Dango Maker (JOI18_dango_maker)C++20
33 / 100
15 ms32068 KiB
#include <bits/stdc++.h> #include <climits> using namespace std; #define f first #define s second #define all(a) a.begin(),a.end() #define sz(a) (int)a.size() #define int long long const int N=1e3+5; char M[N][N]; bool hang[N][N],cot[N][N]; string need="&RGW"; int n,m; int dp[N][N][4]; int f(int i,int j,int k){ if(i<1 || i>n || j<1 || j>m) return 0; int &res=dp[i][j][k]; if(res!=-1) return res; res=0; if(cot[i][j]==0 && k==0){ res=max(res,f(i-1,j+1,0ll)+1); } if(hang[i][j]==0){ res=max(res,f(i-1,j+1,2ll)+1); } res=max(res,f(i-1,j+1,max(0ll,k-1))); return res; } void solve(){ cin>>n>>m; for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) cin>>M[i][j]; } for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ for(int k=1;k<=3;++k){ if(i+k-1 > n || M[i+k-1][j]!=need[k]) cot[i][j]=1; if(j+k-1 > m || M[i][j+k-1]!=need[k]) hang[i][j]=1; } } } int ans=0; memset(dp,-1,sizeof(dp)); for(int i=1;i<=n;++i) ans+=f(i,1,0); for(int i=2;i<=m;++i) ans+=f(n,i,0); cout<<ans; } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0); int T=1; while(T--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...