Submission #1308361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308361		wangzhiyi33	Dango Maker (JOI18_dango_maker)	C++20	100 / 100	285 ms	238356 KiB

dango_maker

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#define int long long 
#define fir first
#define sec second

bool ver[30002][3002];
bool hor[3002][3002];
int dp[3002][3002][3];
int mx[6004];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    char a[n+2][m+2];
    for(int q=0;q<=n+1;q++){
        for(int w=0;w<=m+1;w++){
            a[q][w]='.';
        }
    }

    for(int q=1;q<=n;q++){
        for(int w=1;w<=m;w++){
            cin>>a[q][w];
        }
    }

    for(int q=1;q<=n;q++){
        for(int w=1;w<=m;w++){
            if(a[q-1][w]=='R' && a[q][w]=='G' && a[q+1][w]=='W'){
                ver[q][w]=true;
            }
            if(a[q][w-1]=='R' && a[q][w]=='G' && a[q][w+1]=='W'){
                hor[q][w]=true;
            }
        }
    }

    for(int q=1;q<=n;q++){
        for(int w=1;w<=m;w++){
            // ga nambah
            dp[q][w][0]=max({dp[q-1][w+1][0],dp[q-1][w+1][1],dp[q-1][w+1][2]});
            
            // nambah hori
            if(hor[q][w]){
                dp[q][w][1]=max({dp[q-1][w+1][0],dp[q-1][w+1][1]})+1;
            }

            // nambah verti
            if(ver[q][w]){
                dp[q][w][2]=max({dp[q-1][w+1][0],dp[q-1][w+1][2]})+1;
            }

            mx[q+w]=max({mx[q+w],dp[q][w][0],dp[q][w][1],dp[q][w][2]});
        }
    }

    int ans=0;
    for(int q=1;q<=n+m;q++){
        ans+=mx[q];
    }
    cout<<ans<<endl;
}

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