#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 5;
int a[N], delta[N], sum[N], val[N], comp[N], red[N];
int n, rc, m, k, c = 0;
int inside(int r, int c) {
return 0 <= r && r < rc && 0 <= c && c < m;
}
int dr[4] = {-1, 0, 1, 0}, dc[4] = {0, 1, 0, -1};
void dfs(int r, int c, int cid) {
int i = r * m + c;
comp[i] = cid, sum[cid] += a[i];
if (red[i]) delta[cid] -= 3;
else delta[cid] += 1, val[cid] = min(val[cid], a[i]);;
for (int d = 0; d < 4; ++d) if (inside(r + dr[d], c + dc[d])) {
int j = (r + dr[d]) * m + c + dc[d];
if (comp[j]) continue; // visited
if (red[i] || red[j])
dfs(r + dr[d], c + dc[d], cid);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0); cout.tie(0);
cin >> n >> m, rc = n, n *= m;
for (int i = 0; i < n; ++i)
cin >> a[i];
cin >> k;
for (int i = 0, r, c; i < k; ++i)
cin >> r >> c,
red[r * m + c] = 1;
memset(val, 0x3f, sizeof(val));
for (int i = 0; i < n; ++i)
if (!comp[i] && red[i])
c++, dfs(i / m, i % m, c);
int res = 0;
for (int i = 1; i <= c; ++i) {
if (delta[i] < 0)
return cout << "No", 0;
res += sum[i];
if (delta[i] > 0)
res -= val[i];
}
cout << res;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4308 KB |
Output is correct |
2 |
Correct |
4 ms |
4684 KB |
Output is correct |
3 |
Correct |
8 ms |
5588 KB |
Output is correct |
4 |
Correct |
22 ms |
8620 KB |
Output is correct |
5 |
Correct |
65 ms |
18140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4308 KB |
Output is correct |
2 |
Correct |
4 ms |
4692 KB |
Output is correct |
3 |
Correct |
8 ms |
5612 KB |
Output is correct |
4 |
Correct |
28 ms |
8660 KB |
Output is correct |
5 |
Correct |
72 ms |
18124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4308 KB |
Output is correct |
2 |
Correct |
4 ms |
4692 KB |
Output is correct |
3 |
Correct |
9 ms |
5572 KB |
Output is correct |
4 |
Correct |
25 ms |
8552 KB |
Output is correct |
5 |
Correct |
74 ms |
18080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4180 KB |
Output is correct |
2 |
Correct |
4 ms |
4304 KB |
Output is correct |
3 |
Correct |
5 ms |
4696 KB |
Output is correct |
4 |
Correct |
5 ms |
4532 KB |
Output is correct |
5 |
Correct |
10 ms |
5196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4180 KB |
Output is correct |
2 |
Correct |
3 ms |
4180 KB |
Output is correct |
3 |
Correct |
2 ms |
4180 KB |
Output is correct |
4 |
Correct |
3 ms |
4180 KB |
Output is correct |
5 |
Correct |
3 ms |
4180 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4308 KB |
Output is correct |
2 |
Correct |
4 ms |
4684 KB |
Output is correct |
3 |
Correct |
8 ms |
5588 KB |
Output is correct |
4 |
Correct |
22 ms |
8620 KB |
Output is correct |
5 |
Correct |
65 ms |
18140 KB |
Output is correct |
6 |
Correct |
3 ms |
4308 KB |
Output is correct |
7 |
Correct |
4 ms |
4692 KB |
Output is correct |
8 |
Correct |
8 ms |
5612 KB |
Output is correct |
9 |
Correct |
28 ms |
8660 KB |
Output is correct |
10 |
Correct |
72 ms |
18124 KB |
Output is correct |
11 |
Correct |
3 ms |
4308 KB |
Output is correct |
12 |
Correct |
4 ms |
4692 KB |
Output is correct |
13 |
Correct |
9 ms |
5572 KB |
Output is correct |
14 |
Correct |
25 ms |
8552 KB |
Output is correct |
15 |
Correct |
74 ms |
18080 KB |
Output is correct |
16 |
Correct |
2 ms |
4180 KB |
Output is correct |
17 |
Correct |
4 ms |
4304 KB |
Output is correct |
18 |
Correct |
5 ms |
4696 KB |
Output is correct |
19 |
Correct |
5 ms |
4532 KB |
Output is correct |
20 |
Correct |
10 ms |
5196 KB |
Output is correct |
21 |
Correct |
3 ms |
4308 KB |
Output is correct |
22 |
Correct |
5 ms |
4684 KB |
Output is correct |
23 |
Correct |
11 ms |
5692 KB |
Output is correct |
24 |
Correct |
33 ms |
8524 KB |
Output is correct |
25 |
Correct |
66 ms |
18152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4308 KB |
Output is correct |
2 |
Correct |
4 ms |
4684 KB |
Output is correct |
3 |
Correct |
8 ms |
5588 KB |
Output is correct |
4 |
Correct |
22 ms |
8620 KB |
Output is correct |
5 |
Correct |
65 ms |
18140 KB |
Output is correct |
6 |
Correct |
3 ms |
4308 KB |
Output is correct |
7 |
Correct |
4 ms |
4692 KB |
Output is correct |
8 |
Correct |
8 ms |
5612 KB |
Output is correct |
9 |
Correct |
28 ms |
8660 KB |
Output is correct |
10 |
Correct |
72 ms |
18124 KB |
Output is correct |
11 |
Correct |
3 ms |
4308 KB |
Output is correct |
12 |
Correct |
4 ms |
4692 KB |
Output is correct |
13 |
Correct |
9 ms |
5572 KB |
Output is correct |
14 |
Correct |
25 ms |
8552 KB |
Output is correct |
15 |
Correct |
74 ms |
18080 KB |
Output is correct |
16 |
Correct |
2 ms |
4180 KB |
Output is correct |
17 |
Correct |
4 ms |
4304 KB |
Output is correct |
18 |
Correct |
5 ms |
4696 KB |
Output is correct |
19 |
Correct |
5 ms |
4532 KB |
Output is correct |
20 |
Correct |
10 ms |
5196 KB |
Output is correct |
21 |
Correct |
3 ms |
4180 KB |
Output is correct |
22 |
Correct |
3 ms |
4180 KB |
Output is correct |
23 |
Correct |
2 ms |
4180 KB |
Output is correct |
24 |
Correct |
3 ms |
4180 KB |
Output is correct |
25 |
Correct |
3 ms |
4180 KB |
Output is correct |
26 |
Correct |
3 ms |
4308 KB |
Output is correct |
27 |
Correct |
5 ms |
4684 KB |
Output is correct |
28 |
Correct |
11 ms |
5692 KB |
Output is correct |
29 |
Correct |
33 ms |
8524 KB |
Output is correct |
30 |
Correct |
66 ms |
18152 KB |
Output is correct |
31 |
Correct |
102 ms |
23828 KB |
Output is correct |
32 |
Correct |
71 ms |
15452 KB |
Output is correct |
33 |
Correct |
66 ms |
20732 KB |
Output is correct |
34 |
Correct |
66 ms |
14788 KB |
Output is correct |
35 |
Correct |
100 ms |
26380 KB |
Output is correct |