Submission #233900

#	Time	Username	Problem	Language	Result	Execution time	Memory
233900		nicolaalexandra	Dango Maker (JOI18_dango_maker)	C++14	13 / 100	5 ms	512 KiB

dango_maker

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

int Right[DIM][DIM],up[DIM][DIM],dp_right[DIM][DIM],dp_up[DIM][DIM],dp[DIM][DIM];
char a[DIM][DIM];
int n,m,i,j;

int verif_vert (int i, int j){
    if (a[i-2][j] == 'R' && a[i-1][j] == 'G' && a[i][j] == 'W')
        return 1;
    return 0;
}
int verif_oriz (int i, int j){
    if (a[i][j-2] == 'R' && a[i][j-1] == 'G' && a[i][j] == 'W')
        return 1;
    return 0;
}
int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m;
    for (i=1;i<=n;i++){
        cin>>a[i]+1;
        for (j=1;j<=m;j++){
            Right[i][j] = max (Right[i][j],Right[i][j-1]);
            if (j >= 3 && verif_oriz(i,j))
                Right[i][j] = max (Right[i][j],Right[i][j-3] + 1);

            up[i][j] = max (up[i][j],up[i-1][j]);
            if (i >= 3 && verif_vert(i,j))
                up[i][j] = max (up[i][j],up[i-3][j] + 1);
        }

    }

    for (i=3;i<=n;i++){

        dp_right[i][1] = verif_vert(i,1);
        dp_right[i][2] = verif_vert(i,2) + dp_right[i][1];
        dp_right[i][3] = verif_vert(i,3) + dp_right[i][2];

        int cnt = verif_oriz(i-2,3) + verif_oriz(i-1,3) + verif_oriz(i,3);

        dp_right[i][3] = max (dp_right[i][3],cnt);

        for (j=4;j<=m;j++){

            int cnt = 0;
            cnt += verif_vert(i,j);
            dp_right[i][j] = max (dp_right[i][j], dp_right[i][j-1] + cnt);

            cnt += verif_vert (i,j-1);
            dp_right[i][j] = max (dp_right[i][j], dp_right[i][j-2] + cnt);


            cnt += verif_vert (i,j-2);
            dp_right[i][j] = max (dp_right[i][j], dp_right[i][j-3] + cnt);


            cnt = verif_oriz (i-2,j) + verif_oriz (i-1,j) + verif_oriz (i,j);

            dp_right[i][j] = max (dp_right[i][j],dp_right[i][j-3] + cnt);

        }
    }

    for (j=3;j<=m;j++){

        dp_up[1][j] = verif_oriz(1,j);
        dp_up[2][j] = verif_oriz(2,j) + dp_up[1][j];
        dp_up[3][j] = verif_oriz(3,j) + dp_up[2][j];

        int cnt = 0;
        cnt += verif_vert(3,j-2) + verif_vert(3,j-1) + verif_vert(3,j);
        dp_up[3][j] = max (dp_up[i][j],cnt);

        for (i=4;i<=n;i++){

            cnt = verif_oriz(i,j);
            dp_up[i][j] = max (dp_up[i][j],dp_up[i-1][j] + cnt);

            cnt += verif_oriz(i-1,j);
            dp_up[i][j] = max (dp_up[i][j],dp_up[i-2][j] + cnt);

            cnt += verif_oriz(i-2,j);
            dp_up[i][j] = max (dp_up[i][j],dp_up[i-3][j] + cnt);

            cnt = verif_vert (i,j) + verif_vert (i,j-1) + verif_vert (i,j-2);
            dp_up[i][j] = max (dp_up[i][j], dp_up[i-3][j] + cnt);

        }

    }


    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++){
            dp[i][j] = max (dp[i][j-1] + up[i][j], dp[i-1][j] + Right[i][j]);
            if (j >= 3)
                dp[i][j] = max (dp[i][j], dp[i][j-3] + dp_up[i][j]);
            if (i >= 3)
                dp[i][j] = max (dp[i][j], dp[i-3][j] + dp_right[i][j]);
        }

    cout<<dp[n][m];

    return 0;
}

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:26:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         cin>>a[i]+1;
              ~~~~^~

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