제출 #680465

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
680465		Neos	Dango Maker (JOI18_dango_maker)	C++14	0 / 100	17 ms	28788 KiB

dango_maker

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

#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define getBit(x, i) ((x) >> (i) & 1)
#define rep(i, begin, end) for (ll i = (begin); i <= (end); i++)
#define rrep(i, begin, end) for (ll i = (begin); i >= (end); i--)

typedef long long ll;
typedef pair<int, int> ii;

template <class T>
bool minimize(T &a, const T &b) {
    if(a > b) {a = b; return 1;}
    return 0;
}
template <class T>
bool maximize(T &a, const T &b) {
    if(a < b) {a = b; return 1;}
    return 0;
}

const int N = 3e3 + 7, M = 1e6 + 7, oo = 2e9;

int n, m, tot, sz, match[M], mark[N][N];
string a[N];
bool vis[M];
vector<int> adj[M];

int g(int x, int y) {
    if (mark[x][y]) return mark[x][y];
    return mark[x][y] = ++sz;
}

int mcbm(int u) {
    if (vis[u]) return 0;
    vis[u] = 1;
    for (int v: adj[u]) {
        if (match[v] == -1 || mcbm(match[v])) {
            match[v] = u;
            return 1;
        }
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    rep(i, 1, n) cin >> a[i], a[i] = ' ' + a[i];
    rep(i, 1, n) rep(j, 1, m) {
        if (j + 2 <= m) tot += (a[i].substr(j, 3) == "RGW");
        if (i + 2 <= n) tot += (a[i][j] == 'R' && a[i + 1][j] == 'G' && a[i + 2][j] == 'W');
    }
    rep(i, 1, n) rep(j, i, m) {
        // (i, j) right | (j, i) down
        if (j + 2 <= m && j + 2 <= n) {
            if (a[i].substr(j, 3) == "RGW" && a[j][i] == 'R' && a[j + 1][i] == 'G' && a[j + 2][i] == 'W') {
                adj[g(i, j)].pb(g(j, i));
                adj[g(j, i)].pb(g(i, j));
            }
        }

        // (i, j) down | (j, i) right
        if (j <= n && i + 2 <= m && i + 2 <= n) {
            if (a[j].substr(i, 3) == "RGW" && a[i][j] == 'R' && a[i + 1][j] == 'G' && a[i + 2][j] == 'W') {
                adj[g(i, j)].pb(g(j, i));
                adj[g(j, i)].pb(g(i, j));
            }
        }
    }

    int cnt = 0;
    memset(match, -1, sizeof match);
    rep(i, 1, sz) {
        memset(vis, 0, sizeof vis);
        cnt += mcbm(i);
    }
    cout << tot - cnt / 2;
}

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