이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/* * In the name of GOD */
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
#define F first
#define S second
#define mk make_pair
const int N = 1012345, NI = -1123456789;
int n, m, k, ans = 0, t = 0;
vector <int> a[N];
vector <bool> mr[N];
int vis[N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}, dx2[4] = {-1, 1, 1, -1}, dy2[4] = {1, 1, -1, -1}, bad[N], mn[N], ch[N];
vector <int> g[N];
bool val (int x, int y) {
return ((x >= 1) && (y >= 1) && (x <= n) && (y <= m));
}
int h(int x, int y) {
return (x - 1) * m + y;
}
void hal (int x, int y, int d) {
mr[x][y] = false;
ans += a[x][y];
a[x][y] = NI;
for (int i = 0; i < 4; i++) {
if (i == d)
continue;
ans += a[x + dx[i]][y + dy[i]];
a[x + dx[i]][y + dy[i]] = NI;
}
}
void dfs (int v, int p) {
vis[v] = 1;
int x = (v - 1) / m + 1, y = (v - 1) % m + 1;
for (int i = 0; i < 4; i++)
mn[t] = min(a[x + dx[i]][y + dy[i]], mn[t]);
for (int u : g[v]) {
if (u == p)
continue;
if (!vis[u])
dfs(u, v);
else if (vis[u] == 1) {
bad[t]++;
}
}
vis[v] = 2;
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
cin >> n >> m;
for (int i = 0; i < n + 5; i++)
for (int j = 0; j < m + 5; j++) {
mr[i].push_back(false);
a[i].push_back(NI);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
cin >> k;
for (int i = 1; i <= k; i++) {
int x, y;
cin >> x >> y;
x++;
y++;
mr[x][y] = true;
}
for (int x = 1; x <= n; x++) {
for (int y = 1; y <= m; y++) {
for (int i = 0; i < 4; i++) {
if (mr[x][y] && mr[x + dx[i]][y + dy[i]]) {
hal (x, y, i);
hal (x + dx[i], y + dy[i], (i + 2) & 3);
}
if (mr[x][y] && mr[x + dx2[i]][y + dy2[i]]) {
hal (x, y, i);
hal (x + dx2[i], y + dy2[i], (i + 2) & 3);
}
}
}
}
for (int x = 1; x <= n; x++)
for (int y = 1; y <= m; y++) {
if (!mr[x][y])
continue;
ans += a[x][y];
for (int i = 0; i < 4; i++) {
ans += a[x + dx[i]][y + dy[i]];
}
}
for (int x = 1; x <= n; x++) {
for (int y = 1; y <= m; y++) {
for (int i = 0; i < 2; i++) {
if (val(x + 2 * dx[i], y + 2 * dy[i]) && mr[x][y] && mr[x + 2 * dx[i]][y + 2 * dy[i]]) {
int l = h(x, y);
int r = h(x + 2 * dx[i], y + 2 * dy[i]);
ans -= a[x + dx[i]][y + dy[i]];
g[l].push_back(r);
g[r].push_back(l);
}
}
}
}
for (int x = 1; x <= n; x++) {
for (int y = 1; y <= m; y++) {
if (!mr[x][y]) {
continue;
}
int v = h(x, y);
if (vis[v])
continue;
++t;
mn[t] = -NI;
dfs(v, v);
if (bad[t] > 1) {
cout << "No";
exit(0);
}
if (bad[t] == 0)
ans -= mn[t];
}
}
if (ans < 0) {
cout << "No";
} else {
cout << ans;
}
}
# | 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... |