#include <bits/stdc++.h>
#define endl "\n"
#define int long long
#define see(x) cerr<<#x<<"="<<x<<endl;
using namespace std;
const int N = 1002;
int m, n, k, used[N*N], cnt, ans, val[N*N], 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;
ans += val[def[{x,y}]];
spec[def[{x,y}]] = 1;
if (x) {
g[def[{x,y}]].push_back(def[{x-1,y}]);
g[def[{x-1,y}]].push_back(def[{x,y}]);
}
if (y) {
g[def[{x,y}]].push_back(def[{x,y-1}]);
g[def[{x,y-1}]].push_back(def[{x,y}]);
}
if (x < m-1) {
g[def[{x,y}]].push_back(def[{x+1,y}]);
g[def[{x+1,y}]].push_back(def[{x,y}]);
}
if (y < n-1) {
g[def[{x,y}]].push_back(def[{x,y+1}]);
g[def[{x,y+1}]].push_back(def[{x,y}]);
}
}
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:70: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 |
26496 KB |
Output is correct |
3 |
Correct |
49 ms |
32120 KB |
Output is correct |
4 |
Correct |
128 ms |
48888 KB |
Output is correct |
5 |
Runtime error |
382 ms |
102404 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
24704 KB |
Output is correct |
2 |
Correct |
24 ms |
26368 KB |
Output is correct |
3 |
Correct |
50 ms |
32156 KB |
Output is correct |
4 |
Correct |
130 ms |
48888 KB |
Output is correct |
5 |
Runtime error |
376 ms |
102404 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
24704 KB |
Output is correct |
2 |
Correct |
23 ms |
26388 KB |
Output is correct |
3 |
Correct |
51 ms |
31992 KB |
Output is correct |
4 |
Correct |
132 ms |
48888 KB |
Output is correct |
5 |
Runtime error |
370 ms |
102404 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
24064 KB |
Output is correct |
2 |
Correct |
15 ms |
24064 KB |
Output is correct |
3 |
Correct |
35 ms |
27904 KB |
Output is correct |
4 |
Correct |
27 ms |
26488 KB |
Output is correct |
5 |
Correct |
56 ms |
32376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 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 |
15 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 |
26496 KB |
Output is correct |
3 |
Correct |
49 ms |
32120 KB |
Output is correct |
4 |
Correct |
128 ms |
48888 KB |
Output is correct |
5 |
Runtime error |
382 ms |
102404 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
24704 KB |
Output is correct |
2 |
Correct |
23 ms |
26496 KB |
Output is correct |
3 |
Correct |
49 ms |
32120 KB |
Output is correct |
4 |
Correct |
128 ms |
48888 KB |
Output is correct |
5 |
Runtime error |
382 ms |
102404 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |