#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define pb push_back
#define F first
#define S second
#define pii pair<int ,int>
#define all(a) a.begin(),a.end()
#define loop(i,s,e) for(int i=s;i<e;i++)
using namespace std;
const int N = (int)1e6 + 6;
int n, m, k, g[N], okt = 0;
vector<int> vc, adj[N];
int hx[] = {-1, 1, 0, 0};
int hy[] = {0, 0, 1, -1};
bool vis[N], ok[N];
bool valid(int i,int j){return (i >= 0 && i < n && j >= 0 && j < m);}
void dfs(int v){
vis[v] = 1;
if(!ok[v])vc.pb(g[v]);
else okt ++;
for(auto u : adj[v])if(!vis[u])dfs(u);
}
int32_t main(){
// ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 0; i < n; i ++)
for(int j = 0; j < m;j ++){
int v = i*m +j;
cin >> g[v];
ok[v] = vis[v] = 0;
}
cin >> k;
int ans = 0;
for(int i = 0; i < k; i ++){
int x,y;cin >> x >> y;
int v = x*m+y;
// cout << "V : " << v << endl;
ok[v] = 1, ans += g[v];
for(int r = 0;r < 4 ;r ++){
int xx = x + hx[r], yy = y + hy[r];
if (!valid(xx, yy)) continue;
int u = xx*m + yy;
adj[v].pb(u);
adj[u].pb(v);
}
}
for(int r = 0; r < n; r ++){
for(int c = 0; c < m; c ++){
int v = r*m+c;
if(!vis[v] && ok[v]){
okt=0;
vc.clear();
dfs(v);
if(vc.size() < 3*okt){
cout << "No";
return 0;
}
sort(all(vc));
loop(i,1,3*okt+1) ans+=vc[vc.size()-i];
}
}
}
cout << ans << "\n";
return 0;
}
Compilation message
covering.cpp: In function 'int32_t main()':
covering.cpp:57:30: warning: comparison of integer expressions of different signedness: 'std::vector<long int>::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
57 | if(vc.size() < 3*okt){
| ~~~~~~~~~~^~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
23892 KB |
Output is correct |
2 |
Correct |
19 ms |
24092 KB |
Output is correct |
3 |
Correct |
31 ms |
24652 KB |
Output is correct |
4 |
Correct |
72 ms |
26688 KB |
Output is correct |
5 |
Correct |
194 ms |
33728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
23892 KB |
Output is correct |
2 |
Correct |
18 ms |
24016 KB |
Output is correct |
3 |
Correct |
31 ms |
24684 KB |
Output is correct |
4 |
Correct |
70 ms |
26812 KB |
Output is correct |
5 |
Correct |
200 ms |
33808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
23892 KB |
Output is correct |
2 |
Correct |
20 ms |
24100 KB |
Output is correct |
3 |
Correct |
33 ms |
24692 KB |
Output is correct |
4 |
Correct |
81 ms |
26684 KB |
Output is correct |
5 |
Correct |
198 ms |
33860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
Output is correct |
2 |
Correct |
15 ms |
23716 KB |
Output is correct |
3 |
Correct |
23 ms |
24296 KB |
Output is correct |
4 |
Correct |
18 ms |
24148 KB |
Output is correct |
5 |
Correct |
33 ms |
24892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23764 KB |
Output is correct |
3 |
Correct |
12 ms |
23804 KB |
Output is correct |
4 |
Correct |
14 ms |
23764 KB |
Output is correct |
5 |
Correct |
12 ms |
23764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
23892 KB |
Output is correct |
2 |
Correct |
19 ms |
24092 KB |
Output is correct |
3 |
Correct |
31 ms |
24652 KB |
Output is correct |
4 |
Correct |
72 ms |
26688 KB |
Output is correct |
5 |
Correct |
194 ms |
33728 KB |
Output is correct |
6 |
Correct |
14 ms |
23892 KB |
Output is correct |
7 |
Correct |
18 ms |
24016 KB |
Output is correct |
8 |
Correct |
31 ms |
24684 KB |
Output is correct |
9 |
Correct |
70 ms |
26812 KB |
Output is correct |
10 |
Correct |
200 ms |
33808 KB |
Output is correct |
11 |
Correct |
14 ms |
23892 KB |
Output is correct |
12 |
Correct |
20 ms |
24100 KB |
Output is correct |
13 |
Correct |
33 ms |
24692 KB |
Output is correct |
14 |
Correct |
81 ms |
26684 KB |
Output is correct |
15 |
Correct |
198 ms |
33860 KB |
Output is correct |
16 |
Correct |
12 ms |
23764 KB |
Output is correct |
17 |
Correct |
15 ms |
23716 KB |
Output is correct |
18 |
Correct |
23 ms |
24296 KB |
Output is correct |
19 |
Correct |
18 ms |
24148 KB |
Output is correct |
20 |
Correct |
33 ms |
24892 KB |
Output is correct |
21 |
Correct |
14 ms |
23860 KB |
Output is correct |
22 |
Correct |
20 ms |
24064 KB |
Output is correct |
23 |
Correct |
30 ms |
24800 KB |
Output is correct |
24 |
Correct |
68 ms |
26804 KB |
Output is correct |
25 |
Correct |
198 ms |
33616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
23892 KB |
Output is correct |
2 |
Correct |
19 ms |
24092 KB |
Output is correct |
3 |
Correct |
31 ms |
24652 KB |
Output is correct |
4 |
Correct |
72 ms |
26688 KB |
Output is correct |
5 |
Correct |
194 ms |
33728 KB |
Output is correct |
6 |
Correct |
14 ms |
23892 KB |
Output is correct |
7 |
Correct |
18 ms |
24016 KB |
Output is correct |
8 |
Correct |
31 ms |
24684 KB |
Output is correct |
9 |
Correct |
70 ms |
26812 KB |
Output is correct |
10 |
Correct |
200 ms |
33808 KB |
Output is correct |
11 |
Correct |
14 ms |
23892 KB |
Output is correct |
12 |
Correct |
20 ms |
24100 KB |
Output is correct |
13 |
Correct |
33 ms |
24692 KB |
Output is correct |
14 |
Correct |
81 ms |
26684 KB |
Output is correct |
15 |
Correct |
198 ms |
33860 KB |
Output is correct |
16 |
Correct |
12 ms |
23764 KB |
Output is correct |
17 |
Correct |
15 ms |
23716 KB |
Output is correct |
18 |
Correct |
23 ms |
24296 KB |
Output is correct |
19 |
Correct |
18 ms |
24148 KB |
Output is correct |
20 |
Correct |
33 ms |
24892 KB |
Output is correct |
21 |
Correct |
13 ms |
23764 KB |
Output is correct |
22 |
Correct |
12 ms |
23764 KB |
Output is correct |
23 |
Correct |
12 ms |
23804 KB |
Output is correct |
24 |
Correct |
14 ms |
23764 KB |
Output is correct |
25 |
Correct |
12 ms |
23764 KB |
Output is correct |
26 |
Correct |
14 ms |
23860 KB |
Output is correct |
27 |
Correct |
20 ms |
24064 KB |
Output is correct |
28 |
Correct |
30 ms |
24800 KB |
Output is correct |
29 |
Correct |
68 ms |
26804 KB |
Output is correct |
30 |
Correct |
198 ms |
33616 KB |
Output is correct |
31 |
Correct |
472 ms |
59216 KB |
Output is correct |
32 |
Correct |
232 ms |
34736 KB |
Output is correct |
33 |
Correct |
212 ms |
35776 KB |
Output is correct |
34 |
Correct |
210 ms |
34704 KB |
Output is correct |
35 |
Correct |
345 ms |
45968 KB |
Output is correct |