Submission #996315

#	Time	Username	Problem	Language	Result	Execution time	Memory
996315		yanb	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	253 ms	18264 KiB

dango_maker

#include <bits/stdc++.h>
    
using namespace std;
    
#define int long long
#define pii pair<long long, long long>
    
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    vector<vector<char>> a(n, vector<char>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    
    int ans = 0;
    for (int d = 0; d < n + m - 1; d++) {
        int x, y;
        if (d < n) x = d, y = 0;
        else x = n - 1, y = d - n + 1;

        vector<int> dpx(2), dpy(2), dp(2);
        int s = 2;

        while (x >= 0 && y < m) {
            dpx.push_back(0);
            dpy.push_back(0);
            dp.push_back(0);
            s = dpx.size();

            if (x > 0 && x < n - 1 && a[x][y] == 'G' && a[x - 1][y] == 'R' && a[x + 1][y] == 'W') {
                dpx[s - 1] = max(dpx[s - 2], dp[s - 2]) + 1;
            }
            if (y > 0 && y < m - 1 && a[x][y] == 'G' && a[x][y - 1] == 'R' && a[x][y + 1] == 'W') {
                dpy[s - 1] = max(dpy[s - 2], dp[s - 2]) + 1;
            }
            dp[s - 1] = max({dp[s - 2], dpx[s - 2], dpy[s - 2]});

            x--, y++;
        }

        ans += max({dp[s - 1], dpx[s - 1], dpy[s - 1]});
    }

    cout << ans << "\n";
}   

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