oj.uz

Submission #233900

# Submission time Handle Problem Language Result Execution time Memory
233900 2020-05-22T10:09:52 Z nicolaalexandra Dango Maker (JOI18_dango_maker) C++14
13 / 100
 5 ms 512 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Incorrect 5 ms 512 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Incorrect 5 ms 512 KB Output isn't correct
19 Halted 0 ms 0 KB -