제출 #652147

#제출 시각아이디문제언어결과실행 시간메모리
652147KahouT-Covering (eJOI19_covering)C++14
0 / 100
61 ms96952 KiB
/* In the name of God, aka Allah */ #include<bits/stdc++.h> using namespace std; #define F first #define S second #define mk make_pair #define endl '\n' #define kill(x) if (x) return cout << "No" << endl, void(); typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const ll inf = 1e9 + 50; const int N = 1e6 + 50; int m, n, k; vector<ll> grid[N]; vector<int> mark[N]; vector<int> seen[N]; ll mn[N], bk[N]; ll ans; int dx[] = {-1, 0, 1, 0}; int dy[] = {0, 1, 0, -1}; int d2x[] = {-1, 1, 1, -1}; int d2y[] = {1, 1, -1, -1}; vector<int> adj[N]; bool vis[N]; int t; bool val(int x, int y) { return x >= 0 && x < m && y >= 0 && y < n; } bool dojob(int x, int y, int d) { ans += grid[x][y]; grid[x][y] = -inf; mark[x][y] = 0; for (int i = 0; i < 4; i++) { if (i == d) continue; if (!val(x+dx[i], y+dy[i])) { return 1; } ans += grid[x+dx[i]][y+dy[i]]; grid[x+dx[i]][y+dy[i]] = -inf; } return 0; } int f(int x, int y) { return x*n + y; } void dfs(int u, int p) { vis[u] = 1; int x = u/n, y = u%n; ans += grid[x][y]; seen[x][y]= 1; for (int i = 0; i < 4; i++) { if (!val(x+dx[i], y+dy[i]) || seen[x+dx[i]][y+dy[i]]) continue; seen[x+dx[i]][y+dy[i]]= 1; mn[t] = min(mn[t], grid[x+dx[i]][y+dy[i]]); ans += grid[x+dx[i]][y+dy[i]]; } for (int v:adj[u]) { if (v == p) continue; if (!vis[v]) dfs(v, u); else if (vis[v] == 1) bk[t]++; } vis[u] = 2; } void solve() { cin >> m >> n; for (int i = 0; i <= m+5; i++) { grid[i].resize(n+5); mark[i].resize(n+5); seen[i].resize(n+5); } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { cin >> grid[i][j]; } } for (int i = 0; i <= m*n; i++) { mn[i] = inf; } cin >> k; for (int i = 1; i <= k; i++) { int r, c; cin >> r >> c; mark[r][c] = 1; } for (int x = 0; x < m; x++) { for (int y = 0; y < n; y++) { if (!mark[x][y]) continue; if (x == 0) kill(dojob(x, y, 1)); if (y == n-1) kill(dojob(x, y, 2)); if (x == m-1) kill(dojob(x, y, 3)); if (y == 0) kill(dojob(x, y, 4)); for (int i = 0; i < 4; i++) { if (val(x+dx[i], y+dy[i]) && mark[x][y] && mark[x+dx[i]][y+dy[i]]) { kill(dojob(x, y, i)); kill(dojob(x+dx[i], y+dy[i], (i+2)&3)); } if (val(x+d2x[i], y+d2y[i]) && mark[x][y] && mark[x+d2x[i]][y+d2y[i]]) { kill(dojob(x, y, i)); kill(dojob(x+d2x[i], y+d2y[i], (i+2)&3)); } } } } for (int x = 0; x < m; x++) { for (int y = 0; y < n; y++) { if (!mark[x][y]) continue; for (int i = 0; i < 2; i++) { if (val(x+2*dx[i], y+2*dy[i]) && mark[x+2*dx[i]][y+2*dy[i]]) { int u = f(x, y); int v = f(x+2*dx[i], y+2*dy[i]); adj[u].push_back(v); adj[v].push_back(u); } } } } for (int u = 0; u < n*m; u++) { if (!vis[u] && mark[u/n][u%n]) { t++; dfs(u, u); if (bk[t] >= 2) { cout << "No" << endl; return; } if (!bk[t]) ans -= mn[t]; } } if (ans < 0) { cout << "No" << endl; return; } cout << ans << endl; } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); solve(); 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...