제출 #937977

#제출 시각아이디문제언어결과실행 시간메모리
937977kitlixDango Maker (JOI18_dango_maker)C++17
33 / 100
160 ms262172 KiB
#include <bits/stdc++.h> using namespace std; const int INF = 1e9; vector<vector<int>> g; vector<int> used, mt; int timer = 1; bool kuhn(int v) { if (used[v] == timer) return false; used[v] = timer; for (auto to : g[v]) { if (mt[to] == -1) { mt[v] = to; mt[to] = v; return true; } } for (auto to : g[v]) { if (kuhn(mt[to])) { mt[v] = to; mt[to] = v; return true; } } return false; } signed main() { ios_base::sync_with_stdio(0), cin.tie(0); int n, m; cin >> n >> m; vector<vector<int>> table(n, vector<int>(m)); for (auto& r : table) { string s; cin >> s; for (int j = 0; j < m; ++j) { if (s[j] == 'R') r[j] = 0; else if (s[j] == 'G') r[j] = 1; else r[j] = 2; } } g.resize(2 * n * m), used.resize(n * m), mt.resize(2 * n * m, -1); auto encode = [&](int x, int y) { return x * m + y; }; int allcnt = 0; vector<vector<int>> has_vert(n, vector<int>(m)); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (table[i][j]) continue; if (i + 2 < n) { if (table[i + 1][j] == 1 && table[i + 2][j] == 2) { allcnt += 1; has_vert[i][j] = 1; } } } } for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (table[i][j]) continue; if (j + 2 < m) { if (table[i][j + 1] == 1 && table[i][j + 2] == 2) { allcnt += 1; if (has_vert[i][j]) g[encode(i, j)].push_back(n * m + encode(i, j)); if (i - 1 >= 0 && j + 1 < m && has_vert[i - 1][j + 1]) g[encode(i, j)].push_back(n * m + encode(i - 1, j + 1)); if (i - 2 >= 0 && j + 2 < m && has_vert[i - 2][j + 2]) g[encode(i, j)].push_back(n * m + encode(i - 2, j + 2)); } } } } for (int i = 0; i < n * m; ++i) if (kuhn(i)) timer += 1; int bipmt = 0; for (int i = 0; i < n * m; ++i) if (mt[i] != -1) bipmt += 1; cout << allcnt - bipmt; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...