제출 #160646

#제출 시각아이디문제언어결과실행 시간메모리
160646XCoderDango Maker (JOI18_dango_maker)C++14
100 / 100
1751 ms195212 KiB
#include <bits/stdc++.h>

#define FOR(i,s,e) for(int i=(s);i<(int)(e);i++)
#define FOE(i,s,e) for(int i=(s);i<=(int)(e);i++)
#define REP(i,n)   FOR(i,0,n)
#define ALL(x) (x).begin(), (x).end()
#define CLR(s) memset(s,0,sizeof(s))
#define PB push_back

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pll;
typedef map<int,int> mii;
typedef vector<int> vi;

const int MX_N = 3333;
int DP[MX_N * 2][MX_N][2];
bool v[MX_N][MX_N];
bool h[MX_N][MX_N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    cin >> N >> M;
    string S[N]; REP(i, N) cin >> S[i];
    FOR(i, 2, N) REP(j, M) v[i][j] = (string("") + S[i - 2][j] + S[i - 1][j] + S[i][j] == "RGW");
    FOR(j, 2, M) REP(i, N) h[i][j] = (string("") + S[i][j - 2] + S[i][j - 1] + S[i][j] == "RGW");

    FOE(k, 0, N + M - 2) FOR(i, 0, N) {
        int j = k - i;
        if (i > 0) {
            DP[k][i][0] = DP[k][i - 1][0];
            DP[k][i][1] = max(DP[k][i - 1][1], DP[k][i - 1][0]);
        }
        if (i >= 3) {
            //printf("[%d][%d]->%d\n", i, j, DP[k][i-3][1]);
            DP[k][i][0] = max(DP[k][i][0], DP[k][i - 3][1]);
        }
        if (j >= 0 && j < M) {
            DP[k][i][0] += (int) v[i][j]; // vertical (or horizontal)
            DP[k][i][1] += (int) h[i][j]; // horizontal
        }

        /*
        if (j >= 0 && j < M) {
            if (v[i][j])
                printf("[%d][%d] = V\n", i, j);
            if (h[i][j])
                printf("[%d][%d] = H\n", i, j);
        }
        if (k == 4) printf("[%d][%d] = %d, %d\n", i, j, DP[k][i][0], DP[k][i][1]);
        */
    }

    int Ans = 0;
    FOE(k, 0, N + M - 2) Ans += max(DP[k][N - 1][1], DP[k][N - 1][0]);// cout << DP[k][N - 1][1] << endl;

    cout << Ans << endl;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...