Submission #1276707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276707		coderg300711	Dango Maker (JOI18_dango_maker)	C++20	100 / 100	433 ms	10540 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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

using pii = pair<int, int>;
string rgw = "RGW";

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    int N, M;
    cin >> N >> M;
    vector<string> A(N);
    for (int i = 0; i < N; ++i)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 0;
            }
            it++;
        }
        return 1;
    };
    int ans = 0;
    for (int ss = 0; ss < N + M - 1; ++ss) {
        int ns = min({N, ss + 1, N + M - 1 - ss});
        vector<vector<int>> f(ns + 1, vector<int>(3));
        for (int k = 0, i = min(ss, N - 1); k < ns; ++k, --i) {
            int j = ss - i;
            for (int l = 0; l < 3; ++l) {
                chmax(f[k + 1][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 += max({f[ns][0], f[ns][1], f[ns][2]});
    }
    cout<<ans<<'\n';

    return 0;
}

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