제출 #837652

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
837652		Koyote	Dango Maker (JOI18_dango_maker)	C++11	100 / 100	288 ms	18004 KiB

dango_maker

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

const int maxN = 3e3 + 2;
char mat[maxN][maxN], str[maxN][3];
int dp[maxN][3];

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m; cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) cin >> mat[i][j];

    int ans = 0;
    for (int i = 1; i < n + m - 2; i++) {
        memset(str, 0, sizeof(str));
        memset(dp, 0, sizeof(dp));

        for (int j = 0; j < m; j++) {
            for (int k = 0; k < 3; k++) {
                int r = i + k - 1 - j, c = j;
                if (r < 0 || r >= n) continue;
                str[j][k] = mat[r][c];
            }
        }

        for (int j = 0; j < m; j++) {
            for (int k = 0; k < 3; k++) {
                dp[j + 1][0] = max(dp[j + 1][0], dp[j][k]);
                if (str[j][1] != 'G') continue;
                if (j && k != 1 && str[j - 1][0] == 'R' && str[j + 1][2] == 'W') 
                    dp[j + 1][2] = max(dp[j + 1][2], dp[j][k] + 1);
                if (k != 2 && str[j][0] == 'R' && str[j][2] == 'W') 
                    dp[j + 1][1] = max(dp[j + 1][1], dp[j][k] + 1);
            }
        }
        ans += max({dp[m][0], dp[m][1], dp[m][2]});
    }
    cout << ans << '\n';
}

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