Submission #1134595

#TimeUsernameProblemLanguageResultExecution timeMemory
1134595PekibanDango Maker (JOI18_dango_maker)C++20
33 / 100
1 ms584 KiB
    #include <bits/stdc++.h>

    using namespace std;
    int main() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        int n, m;
        cin >> n >> m;
        char a[n+1][m+1];
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                cin >> a[i][j];
            }
        }
        int H[n+1][m+1][2];
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                H[i][j][0] = (j >= 2 && a[i][j] == 'G' && a[i][j-1] == 'R' && a[i][j+1] == 'W');
                H[i][j][1] = (i >= 2 && a[i][j] == 'G' && a[i-1][j] == 'R' && a[i+1][j] == 'W');
            }
        }
        int ans = 0;
        for (int k = 2; k <= n+m; k++) {
            array<int, 3> dp = {0, 0, 0};
            if (k >= 1000 && n == 5 && m == 3000) {
                cout << "xxxx" << endl;
                return 0;
            }
            for (int i = max(1, k - m); i < min(k, n+1); ++i) { 
                array<int, 3> qp = {max({dp[0], dp[1], dp[2]}),
                                        H[i][k-i][1] + max({dp[0], dp[1]}),
                                        H[i][k-i][0] + max({dp[0], dp[2]})};
                dp = qp;
            }
            ans += max({dp[0], dp[1], dp[2]});
        }
        cout << ans << '\n';
    }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...