Submission #680469

#	Time	Username	Problem	Language	Result	Execution time	Memory
680469		Neos	Dango Maker (JOI18_dango_maker)	C++14	33 / 100	2076 ms	32472 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);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    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(i1, 1, n) rep(j1, 1, m) rep(i2, 1, n) rep(j2, 1, m) {
        if (!(i1 + j1 == i2 + j2)) continue;
        // (i1, j1) right | (i2, j2) down
        if (j1 + 2 <= m && i2 + 2 <= n) {
            if (!(ii(i1, j1) == ii(i2, j2) || ii(i1, j1 + 1) == ii(i2 + 1, j2) || ii(i1, j1 + 2) == ii(i2 + 2, j2)))
                continue;
            if (a[i1].substr(j1, 3) == "RGW" && a[i2][j2] == 'R' && a[i2 + 1][j2] == 'G' && a[i2 + 2][j2] == 'W') {
                adj[g(i1, j1)].pb(tot + g(i2, j2));
            }
        }
    }

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

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