This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/* 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 < n*m; 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, 0);
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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |