제출 #652182

#제출 시각아이디문제언어결과실행 시간메모리
652182KahouT-Covering (eJOI19_covering)C++14
25 / 100
131 ms95436 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 int inf = 1e9 + 50;
const int N = 1e6 + 50;
int m, n, k;
vector<ll> grid[N];
vector<bool> mark[N];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int dx2[] = {-1, 1, 1, -1};
int dy2[] = {1, 1, -1, -1};

ll ans;
int t;
int bk[N];
ll mn[N];
vector<int> adj[N];
bool vis[N];

bool val(int x, int y) {
	return x >= 1 && x <= m && y >= 1 && y <= n;
}

int f(int x, int y) {
	return (x-1)*n + y;
}

void dojob(int x, int y, int d) {
	ans += grid[x][y];
	mark[x][y] = 0;
	grid[x][y] = -inf;
	for (int i = 0; i < 4; i++) {
		if (i == d) continue;
		ans += grid[x+dx[i]][y+dy[i]];
		mark[x+dx[i]][y+dy[i]] = 0;
		grid[x+dx[i]][y+dy[i]] = -inf;
	}
}

void dfs(int u, int p) {
	vis[u] = 1;
	int x = (u-1)/n+1, y = (u-1)%n+1;
	for (int i = 0; i < 4; i++) {
		mn[t] = min(grid[x+dx[i]][y+dy[i]], mn[t]);
	}
	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 r = 0; r < m+5; r++) {
		grid[r].resize(n+5);
		mark[r].resize(n+5);
		for (int c = 0; c < n+5; c++) {
			grid[r][c] = -inf;
		}
	}
	for (int r = 1; r <= m; r++) {
		for (int c = 1; c <= n; c++) {
			cin >> grid[r][c];
		}
	}
	cin >> k;
	for (int i = 1; i <= k; i++) {
		int x,y;
		cin >> x >> y;
		x++, y++;
		mark[x][y] = 1;
	}

	for (int x = 1; x <= m; x++) {
		for (int y = 1; y <= n; y++) {
			for (int i = 0; i < 4; i++) {
				if (mark[x][y] && mark[x+dx[i]][y+dy[i]]) {
					dojob(x, y, i);
					dojob(x+dx[i], y+dy[i], (i+2)&3);
				}
				if (mark[x][y] && mark[x+dx2[i]][y+dy2[i]]) {
					dojob(x, y, i);
					dojob(x+dx2[i], y+dy2[i], (i+2)&3);
				}
			}
		}
	}
	for (int x = 1; x <= m; x++) {
		for (int y = 1; y <= n; y++) {
			if (!mark[x][y]) continue;
			ans += grid[x][y];
			for (int i = 0; i < 4; i++) {
				ans += grid[x+dx[i]][y+dy[i]];
			}
		}
	}
	for (int x = 1; x <= m; x++) {
		for (int y = 1; y <= n; y++) {
			for (int i = 0; i < 4; i++) {
				if (val(x+2*dx[i], y+2*dy[i]) && mark[x][y] && 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]);
					ans -= grid[x+dx[i]][y+dy[i]];
					adj[u].push_back(v);
				}
			}

		}
	}
	for (int x = 1; x <= m; x++) {
		for (int y = 1; y <= n; y++) {
			if (mark[x][y]) {
				int u = f(x,y);
				if (vis[u]) continue;
				t++;
				mn[t] = inf;
				dfs(u, u);
				kill(bk[t] > 1);
				if (!bk[t]) {
					ans -= mn[t];
				}
			}
		}
	}
	kill(ans < 0);
	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...