Submission #365772

#TimeUsernameProblemLanguageResultExecution timeMemory
365772dolphingarlicDango Maker (JOI18_dango_maker)C++14
100 / 100
347 ms124920 KiB
#include <bits/stdc++.h>
using namespace std;

string grid[3000];
int dp[3002][3002][3], prv = 0;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> grid[i];
    for (int diag = 2; diag <= n + m - 2; diag++) {
        for (int i = 0; i < n; i++) {
            int j = diag - i;
            if (j < 0 || j >= m) continue;
            dp[i][j][0] = prv;
            if (j > 1 && grid[i][j] == 'W' && grid[i][j - 1] == 'G' && grid[i][j - 2] == 'R')
                dp[i][j][1] = prv + 1;
            if (i > 1 && grid[i][j] == 'W' && grid[i - 1][j] == 'G' && grid[i - 2][j] == 'R') {
                if (j == m - 1) dp[i][j][2] = prv + 1;
                else if (j == m - 2) dp[i][j][2] = max(dp[i - 1][j + 1][2], dp[i - 1][j + 1][0]) + 1;
                else dp[i][j][2] = max({dp[i - 1][j + 1][2], dp[i - 2][j + 2][2], dp[i - 2][j + 2][0]}) + 1;
            }
            prv = *max_element(dp[i][j], dp[i][j] + 3);
        }
    }
    cout << prv;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...