Submission #1275535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275535		MisterReaper	Dango Maker (JOI18_dango_maker)	C++20	100 / 100	425 ms	10544 KiB

dango_maker

// File dangomaker.cpp created on 02.10.2025 at 19:39:09
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

template<typename T>
bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

using pii = std::pair<int, int>;

std::string rgw = "RGW";

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, M;
    std::cin >> N >> M;

    std::vector<std::string> A(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
    }

    auto check = [&](pii a, pii b, pii c) -> bool {
        int it = 0;
        for (auto[x, y] : {a, b, c}) {
            if (!(0 <= x && x < N && 0 <= y && y < M && A[x][y] == rgw[it])) {
                return false;
            }
            it++;
        }
        return true;
    };

    int ans = 0;

    for (int ss = 0; ss < N + M - 1; ++ss) {
        int ns = std::min({N, ss + 1, N + M - 1 - ss});
        debug(ss, ns);

        std::vector<std::vector<int>> f(ns + 1, std::vector<int>(3));
        for (int k = 0, i = std::min(ss, N - 1); k < ns; ++k, --i) {
            int j = ss - i;
            for (int l = 0; l < 3; ++l) {
                chmax(f[k + 1][std::max(0, l - 1)], f[k][l]);
                if (check({i, j}, {i, j + 1}, {i, j + 2})) {
                    chmax(f[k + 1][2], f[k][l] + 1);
                }
            }
            if (check({i, j}, {i + 1, j}, {i + 2, j})) {
                chmax(f[k + 1][0], f[k][0] + 1);
            }
        }

        ans += std::max({f[ns][0], f[ns][1], f[ns][2]});
    }

    std::cout << ans << '\n';
 
    return 0;
}

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