Submission #1196265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196265		Newtonabc	Dango Maker (JOI18_dango_maker)	C++20	100 / 100	229 ms	9300 KiB

dango_maker

#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;
}

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 67 / 67