Submission #537622

#	Time	Username	Problem	Language	Result	Execution time	Memory
537622		79brue	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	846 ms	44448 KiB

dango_maker

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m;
int arr[3002][3002];
int ans;

int state[3002];
int DP[3002][3];
const int trans[3][3] = {
    0, 1, 1,
    0, 1, -1000000,
    0, -1000000, 1
};

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            char c;
            scanf(" %c", &c);
            if(c=='R') arr[i][j] = 0;
            else if(c=='G') arr[i][j] = 1;
            else arr[i][j] = 2;
        }
    }
    for(int d=3; d<=n+m-1; d++){
        for(int i=1; i<=n; i++){
            state[i] = 0;
            DP[i][0] = DP[i][1] = DP[i][2] = -1e9;

            int j = d-i;
            if(j<1 || j>m || arr[i][j]!=1) continue;
            if(i>1 && i<n && arr[i-1][j]==0 && arr[i+1][j]==2) state[i] |= 1;
            if(j>1 && j<m && arr[i][j-1]==0 && arr[i][j+1]==2) state[i] |= 2;
        }

        for(int i=1; i<=n; i++){
            for(int j=0; j<3; j++){
                for(int k=0; k<3; k++){
                    if((k==1 && !(state[i]&1)) || (k==2 && !(state[i]&2))) continue;
                    DP[i][k] = max(DP[i][k], DP[i-1][j] + trans[j][k]);
                }
            }
        }
        ans += max({DP[n][0], DP[n][1], DP[n][2]});
    }

    printf("%d", ans);
}

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
dango_maker.cpp:24:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |             scanf(" %c", &c);
      |             ~~~~~^~~~~~~~~~~

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