#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
const int inf=1e9;
int n, m;
vector<int>Sz, Mn, P;
vector<vector<int>>A, B;
void pre(){
Sz.clear(), Mn.clear(), A.clear(), B.clear();
Sz.resize((n+2)*(m+3)+m+2), P.resize((n+2)*(m+3)+m+3), Mn.resize((n+1)*(m+2)+m+3, inf), A.resize(n+5, vector<int>(m+5)), B.resize(n+5, vector<int>(m+5));
for(int i=1;i<P.size();i++){
P[i]=i;
}
}
int trans(int i, int j){
return i*(m+3)+j;
}
int find(int ind){
if(ind==P[ind])
return ind;
return P[ind]=find(P[ind]);
}
bool merge(int a, int b){
int ga=find(a), gb=find(b);
if(ga==gb)
return 0;
if(rand()&1)
swap(ga, gb);
P[ga]=gb;
Sz[gb]+=Sz[ga];
Mn[gb]=min(Mn[gb], Mn[ga]);
return 1;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
pre();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>A[i][j];
}
}
for(int i=1;i<=n;i++){
B[i][0]=B[i][m+1]=1;
}
for(int j=1;j<=m;j++){
B[0][j]=B[n+1][j]=1;
}
int q;
cin>>q;
while(q--){
int i, j;
cin>>i>>j;
i++, j++;
B[i][j]+=inf;
B[i+1][j]++, B[i-1][j]++;
B[i][j+1]++, B[i][j-1]++;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(B[i][j]<inf)
continue;
int cur=trans(i, j);
Sz[cur]=1;
Mn[cur]=min(Mn[cur], A[i+1][j]);
Mn[cur]=min(Mn[cur], A[i-1][j]);
Mn[cur]=min(Mn[cur], A[i][j+1]);
Mn[cur]=min(Mn[cur], A[i][j-1]);
}
}
for(int i=0;i<=n+1;i++){
for(int j=0;j<=m+1;j++){
vector<int>Cur;
if(i!=n+1 && B[i+1][j]>=inf)
Cur.push_back(trans(i+1, j));
if(i && B[i-1][j]>=inf)
Cur.push_back(trans(i-1, j));
if(j!=m+1 && B[i][j+1]>=inf)
Cur.push_back(trans(i, j+1));
if(j && B[i][j-1]>=inf)
Cur.push_back(trans(i, j-1));
if(B[i][j]>=inf)
Cur.push_back(trans(i, j));
for(int l1=0;l1<Cur.size();l1++){
for(int l2=0;l2<Cur.size();l2++){
merge(Cur[l1], Cur[l2]);
}
}
}
}
for(int i=0;i<=n+1;i++){
for(int j=0;j<=m+1;j++){
if(B[i][j]>1 && B[i][j]!=inf){
if(B[i][j]>inf)
Sz[find(trans(i, j))]-=B[i][j]-inf;
else if(i && B[i-1][j]>=inf)
Sz[find(trans(i-1, j))]-=B[i][j]-1;
else if(i!=n+1 && B[i+1][j]>=inf)
Sz[find(trans(i+1, j))]-=B[i][j]-1;
else if(j && B[i][j-1]>=inf)
Sz[find(trans(i, j-1))]-=B[i][j]-1;
else
Sz[find(trans(i, j+1))]-=B[i][j]-1;
}
}
}
int ans=0;
for(int i=0;i<P.size();i++){
if(i!=find(i))
continue;
if(Sz[i]<0)
return cout<<"No", 0;
else if(Sz[i]==1){
ans-=Mn[i];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(B[i][j])
ans+=A[i][j];
}
}
cout<<ans;
}
Compilation message
covering.cpp: In function 'void pre()':
covering.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for(int i=1;i<P.size();i++){
| ~^~~~~~~~~
covering.cpp: In function 'int main()':
covering.cpp:91:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for(int l1=0;l1<Cur.size();l1++){
| ~~^~~~~~~~~~~
covering.cpp:92:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for(int l2=0;l2<Cur.size();l2++){
| ~~^~~~~~~~~~~
covering.cpp:115:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for(int i=0;i<P.size();i++){
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
852 KB |
Output is correct |
3 |
Correct |
6 ms |
2356 KB |
Output is correct |
4 |
Correct |
19 ms |
6344 KB |
Output is correct |
5 |
Correct |
63 ms |
20108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
852 KB |
Output is correct |
3 |
Correct |
6 ms |
2260 KB |
Output is correct |
4 |
Correct |
19 ms |
6228 KB |
Output is correct |
5 |
Correct |
62 ms |
20052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
852 KB |
Output is correct |
3 |
Correct |
6 ms |
2332 KB |
Output is correct |
4 |
Correct |
18 ms |
6228 KB |
Output is correct |
5 |
Correct |
81 ms |
20032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
4 ms |
1620 KB |
Output is correct |
4 |
Correct |
3 ms |
1108 KB |
Output is correct |
5 |
Correct |
7 ms |
3028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
852 KB |
Output is correct |
3 |
Correct |
6 ms |
2356 KB |
Output is correct |
4 |
Correct |
19 ms |
6344 KB |
Output is correct |
5 |
Correct |
63 ms |
20108 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
2 ms |
852 KB |
Output is correct |
8 |
Correct |
6 ms |
2260 KB |
Output is correct |
9 |
Correct |
19 ms |
6228 KB |
Output is correct |
10 |
Correct |
62 ms |
20052 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
2 ms |
852 KB |
Output is correct |
13 |
Correct |
6 ms |
2332 KB |
Output is correct |
14 |
Correct |
18 ms |
6228 KB |
Output is correct |
15 |
Correct |
81 ms |
20032 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
340 KB |
Output is correct |
18 |
Correct |
4 ms |
1620 KB |
Output is correct |
19 |
Correct |
3 ms |
1108 KB |
Output is correct |
20 |
Correct |
7 ms |
3028 KB |
Output is correct |
21 |
Correct |
1 ms |
468 KB |
Output is correct |
22 |
Correct |
2 ms |
852 KB |
Output is correct |
23 |
Correct |
7 ms |
2260 KB |
Output is correct |
24 |
Correct |
19 ms |
6356 KB |
Output is correct |
25 |
Correct |
62 ms |
20108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
852 KB |
Output is correct |
3 |
Correct |
6 ms |
2356 KB |
Output is correct |
4 |
Correct |
19 ms |
6344 KB |
Output is correct |
5 |
Correct |
63 ms |
20108 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
2 ms |
852 KB |
Output is correct |
8 |
Correct |
6 ms |
2260 KB |
Output is correct |
9 |
Correct |
19 ms |
6228 KB |
Output is correct |
10 |
Correct |
62 ms |
20052 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
2 ms |
852 KB |
Output is correct |
13 |
Correct |
6 ms |
2332 KB |
Output is correct |
14 |
Correct |
18 ms |
6228 KB |
Output is correct |
15 |
Correct |
81 ms |
20032 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
340 KB |
Output is correct |
18 |
Correct |
4 ms |
1620 KB |
Output is correct |
19 |
Correct |
3 ms |
1108 KB |
Output is correct |
20 |
Correct |
7 ms |
3028 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
0 ms |
212 KB |
Output is correct |
24 |
Correct |
0 ms |
212 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
468 KB |
Output is correct |
27 |
Correct |
2 ms |
852 KB |
Output is correct |
28 |
Correct |
7 ms |
2260 KB |
Output is correct |
29 |
Correct |
19 ms |
6356 KB |
Output is correct |
30 |
Correct |
62 ms |
20108 KB |
Output is correct |
31 |
Correct |
107 ms |
22868 KB |
Output is correct |
32 |
Correct |
63 ms |
20204 KB |
Output is correct |
33 |
Correct |
68 ms |
22168 KB |
Output is correct |
34 |
Correct |
61 ms |
20132 KB |
Output is correct |
35 |
Correct |
77 ms |
20072 KB |
Output is correct |