Submission #678616

#	Time	Username	Problem	Language	Result	Execution time	Memory
678616		hotboy2703	Dango Maker (JOI18_dango_maker)	C++14	13 / 100	1 ms	340 KiB

dango_maker

#include<bits/stdc++.h>
using namespace std;
int dp[3010][5];
pair <bool,bool>  tmp[3010];    int n,m;
int get(int x,int y){
    if (x < 0)x = 0;
    if (y < 0)y = 0;
    if (x <= 0 && y <= 0)return 0;
    int res = -1;int r = x - y + 2;
    if (dp[x][r] != -1)return dp[x][r];
    if (x <= 0){
        res = get(x,y-1) + tmp[y].second;
    }
    else if (y <= 0){
        res = get(x-1,y) + tmp[x].first;
    }
    else{
        if (x >= y){
            res = get(x-1,y);
            if (tmp[x].first){
                res = max(res,1 + get(x-1,y-3));
            }
        }
        else{
            res = get(x,y-1);
            if (tmp[y].second){
                res = max(res,1 + get(x,y-1));
            }
        }
    }
    //cout<<x<<' '<<y<<' '<<res<<'\n';
    dp[x][r] = res;
    return res;
}
int solve(){
    memset(dp,-1,sizeof dp);
    return get(n,n);
}
char a[3010][3010];
int main(){

    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>m;
    for (int i = 1;i <= n;i ++){
        string s;
        cin>>s;
        for (int j = 1;j <= m;j ++){
            a[i][j] = s[j-1];
        }
    }
    int ans = 0;
    for (int k = 2;k <= n + m;k ++){
        for (int i =1 ;i <= n;i ++){
            int j = k - i;
            if (1 <= j && j <= m){
                tmp[i].first = (a[i][j] == 'R' && a[i][j+1] == 'G' && a[i][j+2] == 'W');
                tmp[i].second = (a[i][j] == 'R' && a[i+1][j] == 'G' && a[i+2][j] == 'W');
            }
            else{
                tmp[i] = {0,0};
            }

        }
        /*for (int i = 1;i <= n;i ++){
            cout<<tmp[i].first<<' '<<tmp[i].second<<'\n';
        }*/

        ans += solve();
        //cout<<k<<' '<<ans<<'\n';
    }
    cout<<ans<<'\n';
    return 0;
}

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