#pragma GCC optimize("Ofast")
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cstring>
#include <queue>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std;
#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair <int, int>
#define ull unsigned long long
// #define int long long
// #define int unsigned long long
const ll inf = 1e9 + 7;
const ll weirdMod = 998244353;
int x, y, ans, cur;
int a[1000050], idx, n, m;
vector<int> adj[1000050], vec;
bool used[1000050], isred[1000050];
void dfs(int v) {
used[v] = 1;
if (isred[v]) cur++;
else vec.pb(a[v]);
for (int u : adj[v]) {
if (!used[u]) dfs(u);
}
}
void solve() {
cin >> n >> m; idx = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[idx++];
}
} int k;
cin >> k;
for (int i = 1; i <= k; i++) {
cin >> x >> y; x++; y++;
ans += a[(x - 1) * m + y];
isred[(x - 1) * m + y] = 1;
if (x > 1) {
adj[(x - 1) * m + y].pb((x - 2) * m + y);
adj[(x - 2) * m + y].pb((x - 1) * m + y);
} if (x < n) {
adj[(x - 1) * m + y].pb(x * m + y);
adj[x * m + y].pb((x - 1) * m + y);
} if (y > 1) {
adj[(x - 1) * m + y].pb((x - 1) * m + y - 1);
adj[(x - 1) * m + y - 1].pb((x - 1) * m + y);
} if (y < m) {
adj[(x - 1) * m + y].pb((x - 1) * m + y + 1);
adj[(x - 1) * m + y + 1].pb((x - 1) * m + y);
}
} idx = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (!used[idx]) {
vec.clear(); cur = 0;
dfs((i - 1) * m + j);
if (3 * cur > vec.size()) {
cout << "No"; return;
} for (int v : vec) ans += v;
if (3 * cur == vec.size() - 1) {
int mn = 1e9;
for (int v : vec)
mn = min(mn, v);
ans -= mn;
}
} idx++;
}
} cout << ans;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve();
cout << '\n';
}
return 0;
}
Compilation message
covering.cpp: In function 'void solve()':
covering.cpp:70:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | if (3 * cur > vec.size()) {
| ~~~~~~~~^~~~~~~~~~~~
covering.cpp:73:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | if (3 * cur == vec.size() - 1) {
| ~~~~~~~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
26972 KB |
Output is correct |
2 |
Correct |
9 ms |
27228 KB |
Output is correct |
3 |
Correct |
12 ms |
27484 KB |
Output is correct |
4 |
Correct |
23 ms |
28540 KB |
Output is correct |
5 |
Correct |
65 ms |
33508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
26968 KB |
Output is correct |
2 |
Correct |
9 ms |
27228 KB |
Output is correct |
3 |
Correct |
12 ms |
27484 KB |
Output is correct |
4 |
Correct |
34 ms |
28540 KB |
Output is correct |
5 |
Correct |
96 ms |
33876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
26968 KB |
Output is correct |
2 |
Correct |
8 ms |
27224 KB |
Output is correct |
3 |
Correct |
12 ms |
27504 KB |
Output is correct |
4 |
Correct |
23 ms |
28532 KB |
Output is correct |
5 |
Correct |
62 ms |
33528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
26968 KB |
Output is correct |
2 |
Correct |
7 ms |
26972 KB |
Output is correct |
3 |
Correct |
10 ms |
27224 KB |
Output is correct |
4 |
Correct |
10 ms |
27484 KB |
Output is correct |
5 |
Correct |
13 ms |
27668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
26968 KB |
Output is correct |
2 |
Correct |
7 ms |
26972 KB |
Output is correct |
3 |
Correct |
7 ms |
26972 KB |
Output is correct |
4 |
Correct |
7 ms |
27144 KB |
Output is correct |
5 |
Correct |
8 ms |
27104 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
26972 KB |
Output is correct |
2 |
Correct |
9 ms |
27228 KB |
Output is correct |
3 |
Correct |
12 ms |
27484 KB |
Output is correct |
4 |
Correct |
23 ms |
28540 KB |
Output is correct |
5 |
Correct |
65 ms |
33508 KB |
Output is correct |
6 |
Correct |
7 ms |
26968 KB |
Output is correct |
7 |
Correct |
9 ms |
27228 KB |
Output is correct |
8 |
Correct |
12 ms |
27484 KB |
Output is correct |
9 |
Correct |
34 ms |
28540 KB |
Output is correct |
10 |
Correct |
96 ms |
33876 KB |
Output is correct |
11 |
Correct |
7 ms |
26968 KB |
Output is correct |
12 |
Correct |
8 ms |
27224 KB |
Output is correct |
13 |
Correct |
12 ms |
27504 KB |
Output is correct |
14 |
Correct |
23 ms |
28532 KB |
Output is correct |
15 |
Correct |
62 ms |
33528 KB |
Output is correct |
16 |
Correct |
7 ms |
26968 KB |
Output is correct |
17 |
Correct |
7 ms |
26972 KB |
Output is correct |
18 |
Correct |
10 ms |
27224 KB |
Output is correct |
19 |
Correct |
10 ms |
27484 KB |
Output is correct |
20 |
Correct |
13 ms |
27668 KB |
Output is correct |
21 |
Correct |
7 ms |
26972 KB |
Output is correct |
22 |
Correct |
10 ms |
27256 KB |
Output is correct |
23 |
Correct |
14 ms |
27480 KB |
Output is correct |
24 |
Correct |
24 ms |
28508 KB |
Output is correct |
25 |
Correct |
61 ms |
33616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
26972 KB |
Output is correct |
2 |
Correct |
9 ms |
27228 KB |
Output is correct |
3 |
Correct |
12 ms |
27484 KB |
Output is correct |
4 |
Correct |
23 ms |
28540 KB |
Output is correct |
5 |
Correct |
65 ms |
33508 KB |
Output is correct |
6 |
Correct |
7 ms |
26968 KB |
Output is correct |
7 |
Correct |
9 ms |
27228 KB |
Output is correct |
8 |
Correct |
12 ms |
27484 KB |
Output is correct |
9 |
Correct |
34 ms |
28540 KB |
Output is correct |
10 |
Correct |
96 ms |
33876 KB |
Output is correct |
11 |
Correct |
7 ms |
26968 KB |
Output is correct |
12 |
Correct |
8 ms |
27224 KB |
Output is correct |
13 |
Correct |
12 ms |
27504 KB |
Output is correct |
14 |
Correct |
23 ms |
28532 KB |
Output is correct |
15 |
Correct |
62 ms |
33528 KB |
Output is correct |
16 |
Correct |
7 ms |
26968 KB |
Output is correct |
17 |
Correct |
7 ms |
26972 KB |
Output is correct |
18 |
Correct |
10 ms |
27224 KB |
Output is correct |
19 |
Correct |
10 ms |
27484 KB |
Output is correct |
20 |
Correct |
13 ms |
27668 KB |
Output is correct |
21 |
Correct |
7 ms |
26968 KB |
Output is correct |
22 |
Correct |
7 ms |
26972 KB |
Output is correct |
23 |
Correct |
7 ms |
26972 KB |
Output is correct |
24 |
Correct |
7 ms |
27144 KB |
Output is correct |
25 |
Correct |
8 ms |
27104 KB |
Output is correct |
26 |
Correct |
7 ms |
26972 KB |
Output is correct |
27 |
Correct |
10 ms |
27256 KB |
Output is correct |
28 |
Correct |
14 ms |
27480 KB |
Output is correct |
29 |
Correct |
24 ms |
28508 KB |
Output is correct |
30 |
Correct |
61 ms |
33616 KB |
Output is correct |
31 |
Correct |
248 ms |
56940 KB |
Output is correct |
32 |
Correct |
57 ms |
34408 KB |
Output is correct |
33 |
Correct |
72 ms |
35540 KB |
Output is correct |
34 |
Correct |
65 ms |
34276 KB |
Output is correct |
35 |
Correct |
140 ms |
44392 KB |
Output is correct |