#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int MAX = 1e6 + 5;
typedef pair <int, int> pii;
int n, m, k, sol;
int mat[MAX];
vector <int> occ[MAX];
pii specials[MAX];
map <int, set <int>> ls;
set <pii> spec_set;
bool bio[MAX];
int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};
int mini;
pii dfs(int node){
bio[node] = 1;
int tiles = 0, visited = 0;
for(int j = 0; j < 4; j++){
int nx = specials[node].f + dx[j], ny = specials[node].s + dy[j];
if(nx >= 0 && nx < n && ny >= 0 && ny < m && mat[nx * m + ny] != -1 && !spec_set.count({nx, ny})){
tiles++;
mini = min(mini, mat[nx * m + ny]);
mat[nx * m + ny] = -1;
}
}
for(int i : ls[node]){
if(!bio[i]){
pii info = dfs(i);
visited += info.f;
tiles += info.s;
}
}
return {visited + 1, tiles};
}
int main()
{
cin >> n >> m;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++) cin >> mat[i * m + j];
}
cin >> k;
for(int i = 0; i < k; i++){
int x, y;
cin >> x >> y;
specials[i] = {x, y};
spec_set.insert({x, y});
occ[x * m + y].push_back(i);
for(int j = 0; j < 4; j++){
int nx = x + dx[j], ny = y + dy[j];
if(nx >= 0 && nx < n && ny >= 0 && ny < m) occ[nx * m + ny].push_back(i);
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(!occ[i * m + j].empty()){
sol += mat[i * m + j];
for(int a = 0; a < occ[i * m + j].size(); a++){
for(int b = a + 1; b < occ[i * m + j].size(); b++){
ls[occ[i * m + j][a]].insert(occ[i * m + j][b]);
ls[occ[i * m + j][b]].insert(occ[i * m + j][a]);
}
}
}
}
}
//cout << sol << '\n';
for(int i = 0; i < k; i++){
if(bio[i]) continue;
//cout << i << ": ";
mini = 2e9;
pii info = dfs(i);
//assert(info.s >= info.f * 3);
//cout << info.f << ' ' << info.s << '\n';
if(info.s < info.f * 3){
cout << "No";
exit(0);
}
if(info.s > info.f * 3){
sol -= mini;
}
}
cout << sol;
return 0;
}
Compilation message
covering.cpp: In function 'int main()':
covering.cpp:83:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for(int a = 0; a < occ[i * m + j].size(); a++){
| ~~^~~~~~~~~~~~~~~~~~~~~~~
covering.cpp:84:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int b = a + 1; b < occ[i * m + j].size(); b++){
| ~~^~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23820 KB |
Output is correct |
2 |
Correct |
21 ms |
23932 KB |
Output is correct |
3 |
Correct |
39 ms |
24164 KB |
Output is correct |
4 |
Correct |
89 ms |
24996 KB |
Output is correct |
5 |
Correct |
275 ms |
28032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
23756 KB |
Output is correct |
2 |
Correct |
22 ms |
23904 KB |
Output is correct |
3 |
Correct |
40 ms |
24120 KB |
Output is correct |
4 |
Correct |
101 ms |
25048 KB |
Output is correct |
5 |
Correct |
263 ms |
28000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
23848 KB |
Output is correct |
2 |
Correct |
23 ms |
24056 KB |
Output is correct |
3 |
Correct |
39 ms |
24112 KB |
Output is correct |
4 |
Correct |
89 ms |
25020 KB |
Output is correct |
5 |
Correct |
262 ms |
27936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
23812 KB |
Output is correct |
2 |
Correct |
14 ms |
23736 KB |
Output is correct |
3 |
Correct |
26 ms |
23944 KB |
Output is correct |
4 |
Correct |
21 ms |
24168 KB |
Output is correct |
5 |
Correct |
42 ms |
24360 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
23788 KB |
Output is correct |
2 |
Correct |
14 ms |
23684 KB |
Output is correct |
3 |
Correct |
13 ms |
23756 KB |
Output is correct |
4 |
Correct |
14 ms |
23808 KB |
Output is correct |
5 |
Correct |
13 ms |
23724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23820 KB |
Output is correct |
2 |
Correct |
21 ms |
23932 KB |
Output is correct |
3 |
Correct |
39 ms |
24164 KB |
Output is correct |
4 |
Correct |
89 ms |
24996 KB |
Output is correct |
5 |
Correct |
275 ms |
28032 KB |
Output is correct |
6 |
Correct |
17 ms |
23756 KB |
Output is correct |
7 |
Correct |
22 ms |
23904 KB |
Output is correct |
8 |
Correct |
40 ms |
24120 KB |
Output is correct |
9 |
Correct |
101 ms |
25048 KB |
Output is correct |
10 |
Correct |
263 ms |
28000 KB |
Output is correct |
11 |
Correct |
17 ms |
23848 KB |
Output is correct |
12 |
Correct |
23 ms |
24056 KB |
Output is correct |
13 |
Correct |
39 ms |
24112 KB |
Output is correct |
14 |
Correct |
89 ms |
25020 KB |
Output is correct |
15 |
Correct |
262 ms |
27936 KB |
Output is correct |
16 |
Correct |
14 ms |
23812 KB |
Output is correct |
17 |
Correct |
14 ms |
23736 KB |
Output is correct |
18 |
Correct |
26 ms |
23944 KB |
Output is correct |
19 |
Correct |
21 ms |
24168 KB |
Output is correct |
20 |
Correct |
42 ms |
24360 KB |
Output is correct |
21 |
Correct |
16 ms |
23756 KB |
Output is correct |
22 |
Correct |
21 ms |
23956 KB |
Output is correct |
23 |
Correct |
39 ms |
24148 KB |
Output is correct |
24 |
Correct |
89 ms |
25056 KB |
Output is correct |
25 |
Correct |
261 ms |
27892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23820 KB |
Output is correct |
2 |
Correct |
21 ms |
23932 KB |
Output is correct |
3 |
Correct |
39 ms |
24164 KB |
Output is correct |
4 |
Correct |
89 ms |
24996 KB |
Output is correct |
5 |
Correct |
275 ms |
28032 KB |
Output is correct |
6 |
Correct |
17 ms |
23756 KB |
Output is correct |
7 |
Correct |
22 ms |
23904 KB |
Output is correct |
8 |
Correct |
40 ms |
24120 KB |
Output is correct |
9 |
Correct |
101 ms |
25048 KB |
Output is correct |
10 |
Correct |
263 ms |
28000 KB |
Output is correct |
11 |
Correct |
17 ms |
23848 KB |
Output is correct |
12 |
Correct |
23 ms |
24056 KB |
Output is correct |
13 |
Correct |
39 ms |
24112 KB |
Output is correct |
14 |
Correct |
89 ms |
25020 KB |
Output is correct |
15 |
Correct |
262 ms |
27936 KB |
Output is correct |
16 |
Correct |
14 ms |
23812 KB |
Output is correct |
17 |
Correct |
14 ms |
23736 KB |
Output is correct |
18 |
Correct |
26 ms |
23944 KB |
Output is correct |
19 |
Correct |
21 ms |
24168 KB |
Output is correct |
20 |
Correct |
42 ms |
24360 KB |
Output is correct |
21 |
Correct |
14 ms |
23788 KB |
Output is correct |
22 |
Correct |
14 ms |
23684 KB |
Output is correct |
23 |
Correct |
13 ms |
23756 KB |
Output is correct |
24 |
Correct |
14 ms |
23808 KB |
Output is correct |
25 |
Correct |
13 ms |
23724 KB |
Output is correct |
26 |
Correct |
16 ms |
23756 KB |
Output is correct |
27 |
Correct |
21 ms |
23956 KB |
Output is correct |
28 |
Correct |
39 ms |
24148 KB |
Output is correct |
29 |
Correct |
89 ms |
25056 KB |
Output is correct |
30 |
Correct |
261 ms |
27892 KB |
Output is correct |
31 |
Correct |
985 ms |
92372 KB |
Output is correct |
32 |
Correct |
277 ms |
33972 KB |
Output is correct |
33 |
Correct |
285 ms |
36004 KB |
Output is correct |
34 |
Correct |
273 ms |
33732 KB |
Output is correct |
35 |
Correct |
503 ms |
54128 KB |
Output is correct |