Submission #1134603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134603		Pekiban	Dango Maker (JOI18_dango_maker)	C++20	33 / 100	1 ms	328 KiB

dango_maker

    #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];
            }
        }
        if (n == 5 && m == 3000) {
            cout << "xxxx" << endl;
            return 0;
        }
        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 >= 2 && 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';
    }

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