Submission #1170045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170045		AlgorithmWarrior	Dango Maker (JOI18_dango_maker)	C++20	100 / 100	470 ms	115056 KiB

dango_maker

#include <bits/stdc++.h>

using namespace std;

int const INF=1e9;
int const MAX=3005;
int dp[MAX][MAX][3];
int n,m;
char mat[MAX][MAX];

void read(){
    cin>>n>>m;
    int i,j;
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            cin>>mat[i][j];
}

bool ok1(int lin,int col){
    if(mat[lin][col]!='R')
        return 0;
    if(mat[lin][col+1]!='G')
        return 0;
    if(mat[lin][col+2]!='W')
        return 0;
    return 1;
}

bool ok2(int lin,int col){
    if(mat[lin][col]!='R')
        return 0;
    if(mat[lin+1][col]!='G')
        return 0;
    if(mat[lin+2][col]!='W')
        return 0;
    return 1;
}

bool inside(int lin,int col){
    return 0<lin && lin<=n && 0<col && col<=m;
}

void maxself(int& x,int val){
    if(x<val)
        x=val;
}

int solve_diag(int diag){
    int lin=1,col=diag;
    while(!inside(lin,col)){
        ++lin;
        --col;
    }
    dp[lin-1][col+1][1]=-INF;
    dp[lin-1][col+1][2]=-INF;
    while(inside(lin,col)){
        maxself(dp[lin][col][0],dp[lin-1][col+1][0]);
        maxself(dp[lin][col][0],dp[lin-1][col+1][1]);
        maxself(dp[lin][col][0],dp[lin-1][col+1][2]);
        if(ok1(lin,col)){
            maxself(dp[lin][col][1],1+dp[lin-1][col+1][1]);
            if(inside(lin-1,col+1)){
                maxself(dp[lin][col][1],1+dp[lin-2][col+2][0]);
                maxself(dp[lin][col][1],1+dp[lin-2][col+2][1]);
            }
            else
                maxself(dp[lin][col][1],1+dp[lin-1][col+1][0]);
        }
        else
            dp[lin][col][1]=-INF;
        if(ok2(lin,col)){
            maxself(dp[lin][col][2],1+dp[lin-1][col+1][0]);
            maxself(dp[lin][col][2],1+dp[lin-1][col+1][1]);
            maxself(dp[lin][col][2],1+dp[lin-1][col+1][2]);
        }
        else
            dp[lin][col][2]=-INF;
        ++lin;
        --col;
    }
    --lin;
    ++col;
    int ans=0;
    maxself(ans,dp[lin][col][0]);
    maxself(ans,dp[lin][col][1]);
    maxself(ans,dp[lin][col][2]);
    return ans;
}

int solve(){
    int i;
    int sum=0;
    for(i=1;i<=n+m-1;++i)
        sum+=solve_diag(i);
    return sum;
}

int main()
{
    read();
    cout<<solve();
    return 0;
}

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