Submission #704351

#	Time	Username	Problem	Language	Result	Execution time	Memory
704351		1075508020060209tc	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	354 ms	124172 KiB

dango_maker

//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define X first
#define Y second
int n;int m;
string gr[5010];
int dp[3010][3010][3];
int fans[6010];
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
    cin>>gr[i];
    gr[i]="*"+gr[i];
    gr[i]+="*";
}
gr[0]=gr[1];
gr[n+1]=gr[n+1];

for(int i=n;i>=1;i--){
    for(int j=1;j<=m;j++){
        dp[i][j][0]=max({dp[i+1][j-1][0],dp[i+1][j-1][1],dp[i+1][j-1][2]});
        if(gr[i][j]=='G'&&gr[i-1][j]=='R'&&gr[i+1][j]=='W'){
            dp[i][j][1]=max(dp[i+1][j-1][0]+1,dp[i+1][j-1][1]+1);
        }
        if(gr[i][j]=='G'&&gr[i][j-1]=='R'&&gr[i][j+1]=='W'){
            dp[i][j][2]=max(dp[i+1][j-1][0]+1,dp[i+1][j-1][2]+1);
        }
        fans[i+j]=max({fans[i+j],dp[i][j][0],dp[i][j][1],dp[i][j][2]});
    }
}
int ans=0;
for(int i=0;i<=n+m;i++){
    ans+=fans[i];
}
cout<<ans<<endl;

}

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