#include <bits/stdc++.h>
#define endl "\n"
#define int short
#define see(x) cerr<<#x<<"="<<x<<endl;
using namespace std;
const int32_t N = 1002;
int m, n, used[N*N], val[N*N], spec[N*N];
map <pair <int, int>, int> def;
vector <int> g[N*N], values;
int32_t ans, k, cnt;
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] = 1;
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:31:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int i = 0; i < m; ++ i)
^~~
covering.cpp:38:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
cin >> k;
^~~
covering.cpp:76:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (3*cnt > values.size()) {
~~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
24448 KB |
Output is correct |
2 |
Correct |
22 ms |
25600 KB |
Output is correct |
3 |
Runtime error |
71 ms |
57976 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
24448 KB |
Output is correct |
2 |
Correct |
22 ms |
25472 KB |
Output is correct |
3 |
Runtime error |
73 ms |
58360 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
24448 KB |
Output is correct |
2 |
Correct |
23 ms |
25472 KB |
Output is correct |
3 |
Runtime error |
71 ms |
58104 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
23936 KB |
Output is correct |
2 |
Correct |
14 ms |
24064 KB |
Output is correct |
3 |
Runtime error |
57 ms |
53388 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
14 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 |
17 ms |
24448 KB |
Output is correct |
2 |
Correct |
22 ms |
25600 KB |
Output is correct |
3 |
Runtime error |
71 ms |
57976 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
24448 KB |
Output is correct |
2 |
Correct |
22 ms |
25600 KB |
Output is correct |
3 |
Runtime error |
71 ms |
57976 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |