#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mx = 1005;
int val[mx*mx];
int sid[mx*mx];
bool g_vis[mx*mx];
int n, m;
int dx1[4] = {1, 1, 1, 0};
int dy1[4] = {1, 0, -1, 1};
int dx2[2] = {2, 0};
int dy2[2] = {0, 2};
int dx3[4] = {1, -1, 0, 0};
int dy3[4] = {0, 0, 1, -1};
int dx4[5] = {0, 1, -1, 0, 0};
int dy4[5] = {0, 0, 0, -1, 1};
vector<pair<int, int>> heavy_edges;
vector<pair<int, int>> light_edges;
int g_idx[mx*mx];
vector<int> g_vec[mx*mx];
int g_best[mx*mx];
int g_bad[mx*mx];
void add_light(int a, int b) {
g_bad[g_idx[b]]++;
if(g_idx[a] == g_idx[b]) return;
if(g_vec[g_idx[a]].size() > g_vec[g_idx[b]].size()) swap(a, b);
g_best[g_idx[b]] = min(g_best[g_idx[b]], g_best[g_idx[a]]);
g_bad[g_idx[b]] += g_bad[g_idx[a]];
vector<int> & a_vec = g_vec[g_idx[a]];
for(int i : a_vec) {
g_idx[i] = g_idx[b];
g_vec[g_idx[b]].push_back(i);
}
}
void add_heavy(int a, int b) {
add_light(a, b);
g_bad[g_idx[b]]++;
}
main() {
cin >> n >> m;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cin >> val[i*m + j];
}
}
int cnt_spec;
cin >> cnt_spec;
vector<pair<int, int>> spec(cnt_spec + 1);
for(int i = 1; i <= cnt_spec; i++) {
int x, y; cin >> x >> y;
spec[i] = {x, y};
sid[x*m + y] = i;
}
for(int i = 1; i <= cnt_spec; i++) {
auto [x, y] = spec[i];
for(int dir = 0; dir < 4; dir++) {
int nx = x + dx1[dir];
int ny = y + dy1[dir];
if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if(!sid[nx*m + ny]) continue;
heavy_edges.push_back({i, sid[nx*m + ny]});
//if(i == 9) cout << sid[nx][ny] << "," << endl << nx << " " << ny << endl;
//if(sid[nx][ny] == 9) cout << i << "." << endl << nx << " " << ny << endl;
}
for(int dir = 0; dir < 2; dir++) {
int nx = x + dx2[dir];
int ny = y + dy2[dir];
if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if(!sid[nx*m + ny]) continue;
light_edges.push_back({i, sid[nx*m + ny]});
}
}
for(int i = 1; i <= cnt_spec; i++) {
g_idx[i] = i;
g_vec[i] = {i};
g_best[i] = 1e9;
g_bad[i] = 0;
auto [x, y] = spec[i];
for(int dir = 0; dir < 4; dir++) {
int nx = x + dx3[dir];
int ny = y + dy3[dir];
if(nx < 0 || ny < 0 || nx >= n || ny >= m) {
g_bad[i]++;
} else g_best[i] = min(g_best[i], val[nx*m + ny]);
}
}
for(auto [a, b] : light_edges) add_light(a, b);
for(auto [a, b] : heavy_edges) add_heavy(a, b);
ll rem = 0;
for(int i = 1; i <= cnt_spec; i++) {
int id = g_idx[i];
if(g_vis[id]) continue;
g_vis[id] = true;
if(g_bad[id] > g_vec[id].size()) {
cout << "No" << endl;
return 0;
cout << g_bad[id] << ": " << g_vec[id].size() << endl;
for(int j = 0; j < g_vec[id].size(); j++) {
int k = g_vec[id][j];
cout << k << ": ";
cout << spec[k].first << " " << spec[k].second << endl;
}
return 0;
}
if(g_bad[id] == g_vec[id].size()) continue;
rem += g_best[id];
}
ll ans = 0;
for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) {
bool cond = false;
for(int dir = 0; dir < 5; dir++) {
int nx = i + dx4[dir];
int ny = j + dy4[dir];
if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if(sid[nx*m + ny]) cond = true;
}
if(cond) ans += val[i*m + j];
}
ans -= rem;
cout << ans << endl;
}
Compilation message
covering.cpp:39:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
39 | main() {
| ^~~~
covering.cpp: In function 'int main()':
covering.cpp:94:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | if(g_bad[id] > g_vec[id].size()) {
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~~
covering.cpp:98:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for(int j = 0; j < g_vec[id].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~~
covering.cpp:105:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | if(g_bad[id] == g_vec[id].size()) continue;
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
24140 KB |
Output is correct |
2 |
Correct |
21 ms |
24320 KB |
Output is correct |
3 |
Correct |
34 ms |
25084 KB |
Output is correct |
4 |
Correct |
71 ms |
27288 KB |
Output is correct |
5 |
Correct |
207 ms |
34280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
24148 KB |
Output is correct |
2 |
Correct |
22 ms |
24316 KB |
Output is correct |
3 |
Correct |
33 ms |
25036 KB |
Output is correct |
4 |
Correct |
72 ms |
27308 KB |
Output is correct |
5 |
Correct |
214 ms |
34288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
24104 KB |
Output is correct |
2 |
Correct |
19 ms |
24368 KB |
Output is correct |
3 |
Correct |
40 ms |
25048 KB |
Output is correct |
4 |
Correct |
72 ms |
27272 KB |
Output is correct |
5 |
Correct |
214 ms |
34408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
24048 KB |
Output is correct |
2 |
Correct |
13 ms |
24048 KB |
Output is correct |
3 |
Correct |
27 ms |
24364 KB |
Output is correct |
4 |
Correct |
23 ms |
24272 KB |
Output is correct |
5 |
Correct |
32 ms |
24884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
24048 KB |
Output is correct |
2 |
Correct |
12 ms |
24020 KB |
Output is correct |
3 |
Correct |
13 ms |
23944 KB |
Output is correct |
4 |
Correct |
14 ms |
24020 KB |
Output is correct |
5 |
Correct |
12 ms |
24020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
24140 KB |
Output is correct |
2 |
Correct |
21 ms |
24320 KB |
Output is correct |
3 |
Correct |
34 ms |
25084 KB |
Output is correct |
4 |
Correct |
71 ms |
27288 KB |
Output is correct |
5 |
Correct |
207 ms |
34280 KB |
Output is correct |
6 |
Correct |
16 ms |
24148 KB |
Output is correct |
7 |
Correct |
22 ms |
24316 KB |
Output is correct |
8 |
Correct |
33 ms |
25036 KB |
Output is correct |
9 |
Correct |
72 ms |
27308 KB |
Output is correct |
10 |
Correct |
214 ms |
34288 KB |
Output is correct |
11 |
Correct |
14 ms |
24104 KB |
Output is correct |
12 |
Correct |
19 ms |
24368 KB |
Output is correct |
13 |
Correct |
40 ms |
25048 KB |
Output is correct |
14 |
Correct |
72 ms |
27272 KB |
Output is correct |
15 |
Correct |
214 ms |
34408 KB |
Output is correct |
16 |
Correct |
13 ms |
24048 KB |
Output is correct |
17 |
Correct |
13 ms |
24048 KB |
Output is correct |
18 |
Correct |
27 ms |
24364 KB |
Output is correct |
19 |
Correct |
23 ms |
24272 KB |
Output is correct |
20 |
Correct |
32 ms |
24884 KB |
Output is correct |
21 |
Correct |
14 ms |
24100 KB |
Output is correct |
22 |
Correct |
20 ms |
24488 KB |
Output is correct |
23 |
Correct |
33 ms |
25164 KB |
Output is correct |
24 |
Correct |
72 ms |
27316 KB |
Output is correct |
25 |
Correct |
211 ms |
34244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
24140 KB |
Output is correct |
2 |
Correct |
21 ms |
24320 KB |
Output is correct |
3 |
Correct |
34 ms |
25084 KB |
Output is correct |
4 |
Correct |
71 ms |
27288 KB |
Output is correct |
5 |
Correct |
207 ms |
34280 KB |
Output is correct |
6 |
Correct |
16 ms |
24148 KB |
Output is correct |
7 |
Correct |
22 ms |
24316 KB |
Output is correct |
8 |
Correct |
33 ms |
25036 KB |
Output is correct |
9 |
Correct |
72 ms |
27308 KB |
Output is correct |
10 |
Correct |
214 ms |
34288 KB |
Output is correct |
11 |
Correct |
14 ms |
24104 KB |
Output is correct |
12 |
Correct |
19 ms |
24368 KB |
Output is correct |
13 |
Correct |
40 ms |
25048 KB |
Output is correct |
14 |
Correct |
72 ms |
27272 KB |
Output is correct |
15 |
Correct |
214 ms |
34408 KB |
Output is correct |
16 |
Correct |
13 ms |
24048 KB |
Output is correct |
17 |
Correct |
13 ms |
24048 KB |
Output is correct |
18 |
Correct |
27 ms |
24364 KB |
Output is correct |
19 |
Correct |
23 ms |
24272 KB |
Output is correct |
20 |
Correct |
32 ms |
24884 KB |
Output is correct |
21 |
Correct |
12 ms |
24048 KB |
Output is correct |
22 |
Correct |
12 ms |
24020 KB |
Output is correct |
23 |
Correct |
13 ms |
23944 KB |
Output is correct |
24 |
Correct |
14 ms |
24020 KB |
Output is correct |
25 |
Correct |
12 ms |
24020 KB |
Output is correct |
26 |
Correct |
14 ms |
24100 KB |
Output is correct |
27 |
Correct |
20 ms |
24488 KB |
Output is correct |
28 |
Correct |
33 ms |
25164 KB |
Output is correct |
29 |
Correct |
72 ms |
27316 KB |
Output is correct |
30 |
Correct |
211 ms |
34244 KB |
Output is correct |
31 |
Correct |
314 ms |
47804 KB |
Output is correct |
32 |
Correct |
200 ms |
33428 KB |
Output is correct |
33 |
Correct |
211 ms |
36436 KB |
Output is correct |
34 |
Correct |
213 ms |
33048 KB |
Output is correct |
35 |
Correct |
246 ms |
40872 KB |
Output is correct |