Submission #1350989

#TimeUsernameProblemLanguageResultExecution timeMemory
1350989gayDango Maker (JOI18_dango_maker)C++20
33 / 100
379 ms327680 KiB
#include <bits/stdc++.h>
#include <experimental/random>
#include <random>

//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;

using namespace std;

using ld = long double;
using ll = long long;

const ll INF = 1e18, MOD = 1e9 + 7;

void solve();

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int q = 1;
    //cin >> q;
    while (q--) {
        solve();
    }
}

vector<vector<ll>> g;
vector<ll> mt;
vector<ll> used;
ll timer = 1;

bool kun(ll v) {
    if (used[v] == timer) {
        return false;
    }
    used[v] = timer;
    for (auto u : g[v]) {
        if (mt[u] == -1 || kun(mt[u])) {
            mt[u] = v;
            return true;
        }
    }
    return false;
}

void solve() {
    ll 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];
        }
    }
    vector<vector<ll>> vert(n, vector<ll>(m, -1));
    ll id = 0;
    for (int i = 0; i + 2 < n; i++) {
        for (int j = 0; j < m; j++) {
            string s;
            for (int c = 0; c < 3; c++) {
                s += a[i + c][j];
            }
            if (s == "RGW") {
                vert[i][j] = id++;
            }
        }
    }
    vector<vector<ll>> gor(n, vector<ll>(m, -1));
    ll id2 = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j + 2 < m; j++) {
            string s;
            for (int c = 0; c < 3; c++) {
                s += a[i][j + c];
            }
            if (s == "RGW") {
                gor[i][j] = id2++;
            }
        }
    }
    g.resize(id);
    used.resize(id);
    mt.resize(id2, -1);

    vector<pair<ll, ll>> cord = {{0, 0}, {1, 0}, {2, 0},
                                  {0, -1}, {1, -1}, {2, -1},
                                  {0, -2}, {1, -2}, {2, -2}};
    for (int i = 0; i + 2 < n; i++) {
        for (int j = 0; j < m; j++) {
            if (vert[i][j] == -1) continue;
            for (auto [f1, f2] : cord) {
                ll x = i + f1, y = j + f2;
                if (x < 0 || y < 0 || x == n || y == m) continue;
                if (gor[x][y] != -1) {
                    g[vert[i][j]].push_back(gor[x][y]);
                }
            }
        }
    }
    ll ans = id + id2;
    for (int i = 0; i < id; i++) {
        if (kun(i)) {
            ans--;
            timer++;
        }
    }
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...