Submission #1317447

#TimeUsernameProblemLanguageResultExecution timeMemory
1317447nambanana987Dango Maker (JOI18_dango_maker)C++20
100 / 100
519 ms168496 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()

const int N=3e3+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,0)+1);
    }

    if(hang[i][j]==0){
        res=max(res,f(i-1,j+1,2)+1);
    }

    res=max(res,f(i-1,j+1,max(0,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...