Submission #680463

#TimeUsernameProblemLanguageResultExecution timeMemory
680463NeosDango Maker (JOI18_dango_maker)C++14
0 / 100
16 ms28792 KiB
#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, cnt, 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] = ++cnt; } 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'); // (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, tot) { memset(vis, 0, sizeof vis); cnt += mcbm(i); } cout << tot - cnt; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...