Submission #521968

#	Time	Username	Problem	Language	Result	Execution time	Memory
521968		fallingstar	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	168 ms	20264 KiB

dango_maker

#include <iostream>
#include <algorithm>
#include <vector>
#include <array>

using namespace std;

int solve(const vector<int>& a)
{
    int n = a.size();
    vector<array<int, 2>> f(n, {-1, -1});
    if (a[0] & 1) f[0][0] = 1;
    if (a[0] & 2) f[0][1] = 1;
    for (int i = 0; i + 1 < n; ++i)
        for (int j = 0; j < 2; ++j)
            f[i + 1][j] = max(f[i][1 - j], f[i][j] + !!(a[i + 1] & (j + 1)));
    return max(f.back()[0], f.back()[1]);
}

int main()
{
    cin.tie(NULL); ios_base::sync_with_stdio(false);
    int n, m; cin >> n >> m;
    vector<string> tab(n);
    for (int i = 0; i < n; ++i) cin >> tab[i];

    int res = 0;
    vector<vector<bool>> vst(n, vector<bool>(m));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (tab[i][j] == 'G' && !vst[i][j]) {
                vector<int> seq;
                int u = i, v = j;
                while (true) {
                    int x = 0;
                    x |= (u > 0 && u + 1 < n && tab[u - 1][v] == 'R' && tab[u + 1][v] == 'W');
                    x |= (v > 0 && v + 1 < m && tab[u][v - 1] == 'R' && tab[u][v + 1] == 'W') * 2;
                    if (!x) break;
                    vst[u][v] = true;
                    seq.push_back(x);
                    ++u, --v;
                    if (u >= n || v < 0 || tab[u][v] != 'G') break;
                }
                if (!seq.empty()) res += solve(seq);
            }
    cout << res;
    return 0;
}

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