#include <bits/stdc++.h>
#define endl "\n"
#define see(x) cerr<<#x<<"="<<x<<endl;
using namespace std;
const int N = 1002;
int m, n, val[N*N], ans, k, cnt;
bool spec[N*N], used[N*N];
vector <int> g[N*N], values;
void dfs (int v) {
used[v] = true;
if (spec[v]) ++ cnt;
else values.push_back(val[v]);
for (auto i: g[v])
if (!used[i]) dfs(i);
}
int32_t main () {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> m >> n;
int temp = 1;
for (int i = 0; i < m; ++ i)
for (int j = 0; j < n; ++ j) {
int a; cin >> a;
val[temp ++] = a;
}
cin >> k;
for (int i = 0; i < k; ++ i) {
int x, y;
cin >> x >> y;
++ x; ++ y;
int t = (x-1)*n + y,
t1 = (x-2)*n + y,
t2 = (x-1)*n + y - 1,
t3 = x*n + y,
t4 = (x-1)*n + y + 1;
ans += val[t];
spec[t] = true;
if (x > 1) {
g[t].push_back(t1);
g[t1].push_back(t);
}
if (y > 1) {
g[t].push_back(t2);
g[t2].push_back(t);
}
if (x < m) {
g[t].push_back(t3);
g[t3].push_back(t);
}
if (y < n) {
g[t].push_back(t4);
g[t4].push_back(t);
}
}
temp = 1;
for (int i = 0; i < m; ++ i)
for (int j = 0; j < n; ++ j) {
if (!used[temp]) {
values.clear();
cnt = 0;
dfs(temp);
sort(values.rbegin(), values.rend());
if (3*cnt > values.size()) {
cout << "No\n";
return 0;
}
for (int k = 0; k < 3*cnt; ++ k)
ans += values[k];
}
++ temp;
}
cout << ans << endl;
return 0;
}
Compilation message
covering.cpp: In function 'int32_t main()':
covering.cpp:29:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int i = 0; i < m; ++ i)
^~~
covering.cpp:35:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
cin >> k;
^~~
covering.cpp:74:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (3*cnt > values.size()) {
~~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
24064 KB |
Output is correct |
2 |
Correct |
17 ms |
24192 KB |
Output is correct |
3 |
Correct |
22 ms |
24960 KB |
Output is correct |
4 |
Correct |
39 ms |
26872 KB |
Output is correct |
5 |
Correct |
96 ms |
30968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
24064 KB |
Output is correct |
2 |
Correct |
16 ms |
24192 KB |
Output is correct |
3 |
Correct |
22 ms |
24960 KB |
Output is correct |
4 |
Correct |
41 ms |
26872 KB |
Output is correct |
5 |
Correct |
100 ms |
30968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
24064 KB |
Output is correct |
2 |
Correct |
16 ms |
24192 KB |
Output is correct |
3 |
Correct |
22 ms |
24960 KB |
Output is correct |
4 |
Correct |
39 ms |
26872 KB |
Output is correct |
5 |
Correct |
105 ms |
30968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
23936 KB |
Output is correct |
2 |
Correct |
14 ms |
23936 KB |
Output is correct |
3 |
Correct |
19 ms |
24440 KB |
Output is correct |
4 |
Correct |
16 ms |
24320 KB |
Output is correct |
5 |
Correct |
23 ms |
24960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
23936 KB |
Output is correct |
2 |
Correct |
13 ms |
23936 KB |
Output is correct |
3 |
Correct |
13 ms |
23936 KB |
Output is correct |
4 |
Correct |
14 ms |
23936 KB |
Output is correct |
5 |
Correct |
13 ms |
23936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
24064 KB |
Output is correct |
2 |
Correct |
17 ms |
24192 KB |
Output is correct |
3 |
Correct |
22 ms |
24960 KB |
Output is correct |
4 |
Correct |
39 ms |
26872 KB |
Output is correct |
5 |
Correct |
96 ms |
30968 KB |
Output is correct |
6 |
Correct |
14 ms |
24064 KB |
Output is correct |
7 |
Correct |
16 ms |
24192 KB |
Output is correct |
8 |
Correct |
22 ms |
24960 KB |
Output is correct |
9 |
Correct |
41 ms |
26872 KB |
Output is correct |
10 |
Correct |
100 ms |
30968 KB |
Output is correct |
11 |
Correct |
14 ms |
24064 KB |
Output is correct |
12 |
Correct |
16 ms |
24192 KB |
Output is correct |
13 |
Correct |
22 ms |
24960 KB |
Output is correct |
14 |
Correct |
39 ms |
26872 KB |
Output is correct |
15 |
Correct |
105 ms |
30968 KB |
Output is correct |
16 |
Correct |
13 ms |
23936 KB |
Output is correct |
17 |
Correct |
14 ms |
23936 KB |
Output is correct |
18 |
Correct |
19 ms |
24440 KB |
Output is correct |
19 |
Correct |
16 ms |
24320 KB |
Output is correct |
20 |
Correct |
23 ms |
24960 KB |
Output is correct |
21 |
Correct |
15 ms |
24064 KB |
Output is correct |
22 |
Correct |
20 ms |
24192 KB |
Output is correct |
23 |
Correct |
23 ms |
24960 KB |
Output is correct |
24 |
Correct |
41 ms |
26904 KB |
Output is correct |
25 |
Correct |
99 ms |
31024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
24064 KB |
Output is correct |
2 |
Correct |
17 ms |
24192 KB |
Output is correct |
3 |
Correct |
22 ms |
24960 KB |
Output is correct |
4 |
Correct |
39 ms |
26872 KB |
Output is correct |
5 |
Correct |
96 ms |
30968 KB |
Output is correct |
6 |
Correct |
14 ms |
24064 KB |
Output is correct |
7 |
Correct |
16 ms |
24192 KB |
Output is correct |
8 |
Correct |
22 ms |
24960 KB |
Output is correct |
9 |
Correct |
41 ms |
26872 KB |
Output is correct |
10 |
Correct |
100 ms |
30968 KB |
Output is correct |
11 |
Correct |
14 ms |
24064 KB |
Output is correct |
12 |
Correct |
16 ms |
24192 KB |
Output is correct |
13 |
Correct |
22 ms |
24960 KB |
Output is correct |
14 |
Correct |
39 ms |
26872 KB |
Output is correct |
15 |
Correct |
105 ms |
30968 KB |
Output is correct |
16 |
Correct |
13 ms |
23936 KB |
Output is correct |
17 |
Correct |
14 ms |
23936 KB |
Output is correct |
18 |
Correct |
19 ms |
24440 KB |
Output is correct |
19 |
Correct |
16 ms |
24320 KB |
Output is correct |
20 |
Correct |
23 ms |
24960 KB |
Output is correct |
21 |
Correct |
13 ms |
23936 KB |
Output is correct |
22 |
Correct |
13 ms |
23936 KB |
Output is correct |
23 |
Correct |
13 ms |
23936 KB |
Output is correct |
24 |
Correct |
14 ms |
23936 KB |
Output is correct |
25 |
Correct |
13 ms |
23936 KB |
Output is correct |
26 |
Correct |
15 ms |
24064 KB |
Output is correct |
27 |
Correct |
20 ms |
24192 KB |
Output is correct |
28 |
Correct |
23 ms |
24960 KB |
Output is correct |
29 |
Correct |
41 ms |
26904 KB |
Output is correct |
30 |
Correct |
99 ms |
31024 KB |
Output is correct |
31 |
Correct |
361 ms |
56396 KB |
Output is correct |
32 |
Correct |
92 ms |
34552 KB |
Output is correct |
33 |
Correct |
120 ms |
35704 KB |
Output is correct |
34 |
Correct |
103 ms |
34168 KB |
Output is correct |
35 |
Correct |
192 ms |
44528 KB |
Output is correct |