#include <bits/stdc++.h>
using i64 = long long;
std::vector<std::pair<int, int>> dir{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
void ohNo() {
std::cout << "No\n";
exit(0);
}
struct Component {
int sum, size;
int have, mn;
Component() : sum(0), size(0), have(0), mn(1e9) {}
void add_adj(int x) {
sum += x;
have++;
mn = std::min(mn, x);
}
int ans() {
if (size * 3 > have) {
ohNo();
}
return sum - (have - size * 3) * mn;
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::vector a(n + 2, std::vector<int>(m + 2));
std::vector vis(n + 2, std::vector<int>(m + 2, 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
std::cin >> a[i][j];
vis[i][j] = 0;
}
}
int k;
std::cin >> k;
std::vector<int> r(k), c(k);
std::vector<bool> bad(k);
std::vector red(n + 2, std::vector<int>(m + 2, -1));
for (int i = 0; i < k; i++) {
std::cin >> r[i] >> c[i];
r[i]++;
c[i]++;
red[r[i]][c[i]] = i;
vis[r[i]][c[i]]++;
}
for (int i = 0; i < k; i++) {
int x = r[i], y = c[i];
if (~red[x][y + 1]) {
bad[red[x][y + 1]] = bad[i] = true;
vis[x][y - 1]++;
vis[x][y + 2]++;
vis[x - 1][y]++;
vis[x + 1][y]++;
vis[x - 1][y + 1]++;
vis[x + 1][y + 1]++;
}
if (~red[x + 1][y + 1]) {
bad[red[x + 1][y + 1]] = bad[i] = true;
vis[x - 1][y]++;
vis[x][y - 1]++;
vis[x + 1][y]++;
vis[x][y + 1]++;
if (x + 2 > n || y + 2 > m) ohNo();
vis[x + 1][y + 2]++;
vis[x + 2][y + 1]++;
}
if (~red[x - 1][y + 1]) {
bad[red[x - 1][y + 1]] = bad[i] = true;
vis[x][y - 1]++;
vis[x + 1][y]++;
vis[x - 1][y]++;
vis[x][y + 1]++;
if (y + 2 > m || x - 2 < 1) ohNo();
vis[x - 1][y + 2]++;
vis[x - 2][y + 1]++;
}
}
for (int i = 0; i <= n + 1; i++) {
for (int j = 0; j <= m + 1; j++) {
if (vis[i][j] > 1) {
ohNo();
}
}
}
auto counted = vis;
std::vector<Component> comp;
for (int i = 0; i < k; i++) {
if (bad[i]) continue;
std::queue<std::pair<int, int>> que;
que.emplace(r[i], c[i]);
Component nw;
bad[i] = true;
while (!que.empty()) {
auto [x, y] = que.front();
que.pop();
nw.size++;
for (auto [dx, dy] : dir) {
int nx = x + dx, ny = y + dy;
if (!counted[nx][ny]) {
counted[nx][ny] = true;
nw.add_adj(a[nx][ny]);
}
}
for (auto [dx, dy] : dir) {
int nx = x + dx * 2, ny = y + dy * 2;
if (nx < 0 || ny < 0 || nx > n || ny > m) continue;
if (~red[nx][ny] && !bad[red[nx][ny]]) {
bad[red[nx][ny]] = true;
que.emplace(nx, ny);
}
}
}
comp.push_back(nw);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
ans += a[i][j] * vis[i][j];
}
}
for (auto x : comp) {
ans += x.ans();
}
std::cout << ans << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
4 ms |
716 KB |
Output is correct |
3 |
Correct |
10 ms |
1868 KB |
Output is correct |
4 |
Correct |
28 ms |
5156 KB |
Output is correct |
5 |
Correct |
95 ms |
16160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
3 ms |
588 KB |
Output is correct |
3 |
Correct |
10 ms |
1896 KB |
Output is correct |
4 |
Correct |
29 ms |
5164 KB |
Output is correct |
5 |
Correct |
96 ms |
16160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
3 ms |
716 KB |
Output is correct |
3 |
Correct |
10 ms |
1892 KB |
Output is correct |
4 |
Correct |
28 ms |
5160 KB |
Output is correct |
5 |
Correct |
97 ms |
16160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
6 ms |
1228 KB |
Output is correct |
4 |
Correct |
3 ms |
844 KB |
Output is correct |
5 |
Correct |
10 ms |
2188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
4 ms |
716 KB |
Output is correct |
3 |
Correct |
10 ms |
1868 KB |
Output is correct |
4 |
Correct |
28 ms |
5156 KB |
Output is correct |
5 |
Correct |
95 ms |
16160 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
3 ms |
588 KB |
Output is correct |
8 |
Correct |
10 ms |
1896 KB |
Output is correct |
9 |
Correct |
29 ms |
5164 KB |
Output is correct |
10 |
Correct |
96 ms |
16160 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
12 |
Correct |
3 ms |
716 KB |
Output is correct |
13 |
Correct |
10 ms |
1892 KB |
Output is correct |
14 |
Correct |
28 ms |
5160 KB |
Output is correct |
15 |
Correct |
97 ms |
16160 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
6 ms |
1228 KB |
Output is correct |
19 |
Correct |
3 ms |
844 KB |
Output is correct |
20 |
Correct |
10 ms |
2188 KB |
Output is correct |
21 |
Correct |
1 ms |
460 KB |
Output is correct |
22 |
Correct |
4 ms |
716 KB |
Output is correct |
23 |
Correct |
10 ms |
1896 KB |
Output is correct |
24 |
Correct |
28 ms |
5024 KB |
Output is correct |
25 |
Correct |
96 ms |
16176 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
4 ms |
716 KB |
Output is correct |
3 |
Correct |
10 ms |
1868 KB |
Output is correct |
4 |
Correct |
28 ms |
5156 KB |
Output is correct |
5 |
Correct |
95 ms |
16160 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
3 ms |
588 KB |
Output is correct |
8 |
Correct |
10 ms |
1896 KB |
Output is correct |
9 |
Correct |
29 ms |
5164 KB |
Output is correct |
10 |
Correct |
96 ms |
16160 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
12 |
Correct |
3 ms |
716 KB |
Output is correct |
13 |
Correct |
10 ms |
1892 KB |
Output is correct |
14 |
Correct |
28 ms |
5160 KB |
Output is correct |
15 |
Correct |
97 ms |
16160 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
6 ms |
1228 KB |
Output is correct |
19 |
Correct |
3 ms |
844 KB |
Output is correct |
20 |
Correct |
10 ms |
2188 KB |
Output is correct |
21 |
Correct |
0 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
0 ms |
204 KB |
Output is correct |
26 |
Correct |
1 ms |
460 KB |
Output is correct |
27 |
Correct |
4 ms |
716 KB |
Output is correct |
28 |
Correct |
10 ms |
1896 KB |
Output is correct |
29 |
Correct |
28 ms |
5024 KB |
Output is correct |
30 |
Correct |
96 ms |
16176 KB |
Output is correct |
31 |
Correct |
141 ms |
18092 KB |
Output is correct |
32 |
Correct |
100 ms |
16016 KB |
Output is correct |
33 |
Correct |
109 ms |
19812 KB |
Output is correct |
34 |
Correct |
111 ms |
16016 KB |
Output is correct |
35 |
Correct |
115 ms |
16540 KB |
Output is correct |