Submission #1064282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064282		oscar1f	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	248 ms	18516 KiB

dango_maker

#include<bits/stdc++.h>
using namespace std;

//#define int long long

const int TAILLE_MAX=3000+5;
int nbLig,nbCol,rep;
char val[TAILLE_MAX][TAILLE_MAX];
int memo[TAILLE_MAX][8];

int dyna(int lig,int col,int preced) {
    if (lig<0 or col>=nbCol) {
        return 0;
    }
    int ans=memo[lig][preced];
    if (ans!=-1) {
        return ans;
    }
    int coin=4*(preced%2);
    ans=dyna(lig-1,col+1,coin);
    if (preced/2==0 and val[lig][col]=='R' and val[lig+1][col]=='G' and val[lig+2][col]=='W') {
        ans++;
    }
    if (val[lig][col]=='R' and val[lig][col+1]=='G' and val[lig][col+2]=='W') {
        ans=max(ans,dyna(lig-1,col+1,coin+3)+1);
    }
    memo[lig][preced]=ans;
    return ans;
}

void calc(int lig,int col) {
    for (int i=0;i<nbLig;i++) {
        for (int j=0;j<8;j++) {
            memo[i][j]=-1;
        }
    }
    rep+=dyna(lig,col,0);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>nbLig>>nbCol;
    for (int i=0;i<nbLig;i++) {
        for (int j=0;j<nbCol;j++) {
            cin>>val[i][j];
        }
    }
    for (int i=0;i<nbLig;i++) {
        calc(i,0);
    }
    for (int j=1;j<nbCol;j++) {
        calc(nbLig-1,j);
    }
    cout<<rep<<endl;
    return 0;
}
 

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