제출 #284997

#제출 시각아이디문제언어결과실행 시간메모리
284997WLZT-Covering (eJOI19_covering)C++14
30 / 100
83 ms12152 KiB
#include <bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; const vector<int> dx = {0, 0, 1, -1}; const vector<int> dy = {1, -1, 0, 0}; int m, n; vector< vector<int> > grid, special, g; vector<int> r, c; vector<bool> was; set< pair<int, int> > st; int sum, mn; int dfs(int u) { was[u] = true; int ans = 1; sum += grid[r[u]][c[u]]; for (int t = 0; t < 4; t++) { int nr = r[u] + dx[t]; int nc = c[u] + dy[t]; if (nr < 0 || nc < 0 || nr >= m || nc >= n) { continue; } if (!st.count({nr, nc})) { st.insert({nr, nc}); sum += grid[nr][nc]; mn = min(mn, grid[nr][nc]); } } for (auto& v : g[u]) { if (!was[v]) { ans += dfs(v); } } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> m >> n; grid.assign(m, vector<int>(n)); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { cin >> grid[i][j]; } } int k; cin >> k; special.assign(m, vector<int>(n, -1)); r.resize(k); c.resize(k); for (int i = 0; i < k; i++) { cin >> r[i] >> c[i]; special[r[i]][c[i]] = i; } g.resize(k); for (int i = 0; i < k; i++) { set<int> st; for (int t1 = 0; t1 < 4; t1++) { for (int t2 = 0; t2 < 4; t2++) { int nr = r[i] + dx[t1] + dx[t2]; int nc = c[i] + dy[t1] + dy[t2]; if (nr < 0 || nc < 0 || nr >= m || nc >= n) { continue; } st.insert(special[nr][nc]); } } st.erase(i); st.erase(-1); for (auto& x : st) { g[i].push_back(x); } } was.assign(k, false); int ans = 0; for (int i = 0; i < k; i++) { if (!was[i]) { sum = 0; mn = INF; st.clear(); int sz = dfs(i); if ((int) st.size() < 3 * sz) { cout << "No\n"; return 0; } else if ((int) st.size() == 3 * sz) { ans += sum; } else { ans += sum - mn; } } } cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...