#include <bits/stdc++.h>
#define endl "\n"
#define see(x) cerr<<#x<<"="<<x<<endl;
using namespace std;
const int32_t N = 1002;
int m, n, used[N*N], val[N*N], ans, k, cnt;
bool spec[N*N];
map <pair <int, int>, int> def;
vector <int> g[N*N], values;
void dfs (int v) {
used[v] = 1;
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;
def[{i, j}] = temp ++;
}
cin >> k;
for (int i = 0; i < k; ++ i) {
int x, y;
cin >> x >> y;
int t = def[{x,y}],
t1 = def[{x-1,y}],
t2 = def[{x,y-1}],
t3 = def[{x+1,y}],
t4 = def[{x,y+1}];
ans += val[t];
spec[t] = true;
if (x) {
g[t].push_back(t1);
g[t1].push_back(t);
}
if (y) {
g[t].push_back(t2);
g[t2].push_back(t);
}
if (x < m-1) {
g[t].push_back(t3);
g[t3].push_back(t);
}
if (y < n-1) {
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:30:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int i = 0; i < m; ++ i)
^~~
covering.cpp:37:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
cin >> k;
^~~
covering.cpp:75:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (3*cnt > values.size()) {
~~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
24704 KB |
Output is correct |
2 |
Correct |
23 ms |
26112 KB |
Output is correct |
3 |
Correct |
54 ms |
31096 KB |
Output is correct |
4 |
Correct |
132 ms |
45432 KB |
Output is correct |
5 |
Correct |
413 ms |
95480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
24704 KB |
Output is correct |
2 |
Correct |
23 ms |
26112 KB |
Output is correct |
3 |
Correct |
50 ms |
31100 KB |
Output is correct |
4 |
Correct |
124 ms |
45448 KB |
Output is correct |
5 |
Correct |
416 ms |
95480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
24704 KB |
Output is correct |
2 |
Correct |
23 ms |
26112 KB |
Output is correct |
3 |
Correct |
49 ms |
31096 KB |
Output is correct |
4 |
Correct |
134 ms |
45560 KB |
Output is correct |
5 |
Correct |
411 ms |
95480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
24064 KB |
Output is correct |
2 |
Correct |
14 ms |
24064 KB |
Output is correct |
3 |
Correct |
31 ms |
27520 KB |
Output is correct |
4 |
Correct |
24 ms |
26112 KB |
Output is correct |
5 |
Correct |
52 ms |
31096 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 |
13 ms |
23936 KB |
Output is correct |
4 |
Correct |
13 ms |
23936 KB |
Output is correct |
5 |
Correct |
13 ms |
23936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
24704 KB |
Output is correct |
2 |
Correct |
23 ms |
26112 KB |
Output is correct |
3 |
Correct |
54 ms |
31096 KB |
Output is correct |
4 |
Correct |
132 ms |
45432 KB |
Output is correct |
5 |
Correct |
413 ms |
95480 KB |
Output is correct |
6 |
Correct |
17 ms |
24704 KB |
Output is correct |
7 |
Correct |
23 ms |
26112 KB |
Output is correct |
8 |
Correct |
50 ms |
31100 KB |
Output is correct |
9 |
Correct |
124 ms |
45448 KB |
Output is correct |
10 |
Correct |
416 ms |
95480 KB |
Output is correct |
11 |
Correct |
17 ms |
24704 KB |
Output is correct |
12 |
Correct |
23 ms |
26112 KB |
Output is correct |
13 |
Correct |
49 ms |
31096 KB |
Output is correct |
14 |
Correct |
134 ms |
45560 KB |
Output is correct |
15 |
Correct |
411 ms |
95480 KB |
Output is correct |
16 |
Correct |
14 ms |
24064 KB |
Output is correct |
17 |
Correct |
14 ms |
24064 KB |
Output is correct |
18 |
Correct |
31 ms |
27520 KB |
Output is correct |
19 |
Correct |
24 ms |
26112 KB |
Output is correct |
20 |
Correct |
52 ms |
31096 KB |
Output is correct |
21 |
Correct |
16 ms |
24704 KB |
Output is correct |
22 |
Correct |
24 ms |
26232 KB |
Output is correct |
23 |
Correct |
50 ms |
31096 KB |
Output is correct |
24 |
Correct |
128 ms |
45372 KB |
Output is correct |
25 |
Correct |
409 ms |
95608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
24704 KB |
Output is correct |
2 |
Correct |
23 ms |
26112 KB |
Output is correct |
3 |
Correct |
54 ms |
31096 KB |
Output is correct |
4 |
Correct |
132 ms |
45432 KB |
Output is correct |
5 |
Correct |
413 ms |
95480 KB |
Output is correct |
6 |
Correct |
17 ms |
24704 KB |
Output is correct |
7 |
Correct |
23 ms |
26112 KB |
Output is correct |
8 |
Correct |
50 ms |
31100 KB |
Output is correct |
9 |
Correct |
124 ms |
45448 KB |
Output is correct |
10 |
Correct |
416 ms |
95480 KB |
Output is correct |
11 |
Correct |
17 ms |
24704 KB |
Output is correct |
12 |
Correct |
23 ms |
26112 KB |
Output is correct |
13 |
Correct |
49 ms |
31096 KB |
Output is correct |
14 |
Correct |
134 ms |
45560 KB |
Output is correct |
15 |
Correct |
411 ms |
95480 KB |
Output is correct |
16 |
Correct |
14 ms |
24064 KB |
Output is correct |
17 |
Correct |
14 ms |
24064 KB |
Output is correct |
18 |
Correct |
31 ms |
27520 KB |
Output is correct |
19 |
Correct |
24 ms |
26112 KB |
Output is correct |
20 |
Correct |
52 ms |
31096 KB |
Output is correct |
21 |
Correct |
13 ms |
23936 KB |
Output is correct |
22 |
Correct |
14 ms |
23936 KB |
Output is correct |
23 |
Correct |
13 ms |
23936 KB |
Output is correct |
24 |
Correct |
13 ms |
23936 KB |
Output is correct |
25 |
Correct |
13 ms |
23936 KB |
Output is correct |
26 |
Correct |
16 ms |
24704 KB |
Output is correct |
27 |
Correct |
24 ms |
26232 KB |
Output is correct |
28 |
Correct |
50 ms |
31096 KB |
Output is correct |
29 |
Correct |
128 ms |
45372 KB |
Output is correct |
30 |
Correct |
409 ms |
95608 KB |
Output is correct |
31 |
Runtime error |
977 ms |
102404 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
32 |
Halted |
0 ms |
0 KB |
- |