Submission #1110149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110149		Maite_Morale	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	314 ms	86352 KiB

dango_maker

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX 2000005 
#define S second
#define F first
#define pll pair<ll,ll>
#define vll vector<ll>
#define vpll vector<pll>


ll n,m,dp[2][MAX];
string a[MAX];
ll comp(ll z,ll i,ll j){
    pll x={min(i,n-1)-j,max(0LL,i-n+1)+j};
    if(z==0){
        if(x.S-1>=0 && x.S+1<m){
            if(a[x.F][x.S-1]=='R' && a[x.F][x.S]=='G' && a[x.F][x.S+1]=='W')return 1;
            return 0;
        }
        return 0;
    }
    if(x.F-1>=0 && x.F+1<n){
        if(a[x.F-1][x.S]=='R' && a[x.F][x.S]=='G' && a[x.F+1][x.S]=='W')return 1;
        return 0;
    }
return 0;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    ll r=0,h=0;
    for(int i=0;i<n+m-1;i++){
        if(i<n)h++;
        if(i>=m)h--;
        if(i<1)continue;
        for(int j=0;j<h;j++){
            dp[0][j]=dp[1][j]=0;
            if(j>=1){
                dp[0][j]=dp[0][j-1];
                dp[1][j]=dp[1][j-1];
            }
            if(j>=2){
                dp[0][j]=max(dp[0][j],dp[1][j-2]);
                dp[1][j]=max(dp[1][j],dp[0][j-2]);     
            }
            if(comp(0,i,j)==1)dp[0][j]++;
            if(comp(1,i,j)==1)dp[1][j]++;
          //  cout<<"="<<dp[0][j]<<" "<<dp[1][j]<<"\n";
        }
        //cout<<"...\n";
        r+=max(dp[0][h-1],dp[1][h-1]);
    }
    cout<<r<<"\n";
return 0;
}

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