#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF=1e9,MOD=1e9+7;
const ll LINF=1e18;
#define fi first
#define se second
#define pii pair<int,int>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define pb push_back
void PRINT(int x) {cerr << x;}
void PRINT(ll x) {cerr << x;}
void PRINT(double x) {cerr << x;}
void PRINT(char x) {cerr << '\'' << x << '\'';}
void PRINT(string x) {cerr << '\"' << x << '\"';}
void PRINT(bool x) {cerr << (x ? "true" : "false");}
template<typename T,typename V>
void PRINT(pair<T,V>& x){
cerr<<"{";
PRINT(x.fi);
cerr<<",";
PRINT(x.se);
cerr<<"}";
}
template<typename T>
void PRINT(T &x){
int id=0;
cerr<<"{";
for(auto _i:x){
cerr<<(id++ ? "," : "");
PRINT(_i);
}
cerr<<"}";
}
void _PRINT(){
cerr<<"]\n";
}
template<typename Head,typename... Tail>
void _PRINT(Head h,Tail... t){
PRINT(h);
if(sizeof...(t)) cerr<<", ";
_PRINT(t...);
}
#define Debug(x...) cerr<<"["<<#x<<"]=["; _PRINT(x)
int N,M,K;
vector<vector<ll>> a;
set<pii> special,special1;
vector<pii> comp;
set<pair<ll,pii>> adja;
vector<int> di={1,0,-1,0},dj={0,1,0,-1};
vector<int> dis={1,2,0,0,-1,-2,0,0,1,-1,-1,1};
vector<int> djs={0,0,1,2,0,0,-1,-2,1,1,-1,-1};
bool Valid(int i,int j){
return (1<=i && i<=N) && (1<=j && j<=M);
}
void Dfs(int i,int j){
comp.pb({i,j});
special.erase(special.find({i,j}));
for(int d=0;d<12;d++){
int in=i+dis[d],jn=j+djs[d];
if(special.count({in,jn})){
Dfs(in,jn);
}
}
}
void Solve(){
cin>>N>>M;
a.resize(N+1);
for(int i=1;i<=N;i++){
a[i].resize(M+1);
for(int j=1;j<=M;j++){
cin>>a[i][j];
}
}
cin>>K;
for(int i=1;i<=K;i++){
int is,js; cin>>is>>js; is++,js++;
special.insert({is,js});
special1.insert({is,js});
}
//Debug(special);
ll res=0;
while(!special.empty()){
pii p=*special.begin();
Dfs(p.fi,p.se);
//Debug(comp);
for(pii p:comp){
int i=p.fi,j=p.se;
for(int d=0;d<4;d++){
int in=i+di[d];
int jn=j+dj[d];
if(Valid(in,jn) && !special1.count({in,jn})){
adja.insert({a[in][jn],{in,jn}});
}
}
}
//Debug(adja);
int k=sz(comp);
if(sz(adja)<3*k){
cout<<"No"<<endl;
return;
}
else if(sz(adja)==3*k){
for(auto p:adja){
res+=p.fi;
}
for(auto p:comp){
res+=a[p.fi][p.se];
}
}
else{
ll mn=INF;
for(auto p:adja){
res+=p.fi;
mn=min(mn,p.fi);
}
for(auto p:comp){
res+=a[p.fi][p.se];
}
res-=mn;
}
comp.clear();
adja.clear();
}
cout<<res<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t; t=1;
//cin>>t;
while(t--){
Solve();
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
596 KB |
Output is correct |
3 |
Correct |
7 ms |
1480 KB |
Output is correct |
4 |
Correct |
21 ms |
3876 KB |
Output is correct |
5 |
Correct |
70 ms |
12048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
4 ms |
596 KB |
Output is correct |
3 |
Correct |
9 ms |
1492 KB |
Output is correct |
4 |
Correct |
20 ms |
3868 KB |
Output is correct |
5 |
Correct |
62 ms |
12036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
2 ms |
588 KB |
Output is correct |
3 |
Correct |
7 ms |
1492 KB |
Output is correct |
4 |
Correct |
20 ms |
3796 KB |
Output is correct |
5 |
Correct |
60 ms |
12072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
4 ms |
840 KB |
Output is correct |
4 |
Correct |
3 ms |
596 KB |
Output is correct |
5 |
Correct |
8 ms |
1568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
316 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
596 KB |
Output is correct |
3 |
Correct |
7 ms |
1480 KB |
Output is correct |
4 |
Correct |
21 ms |
3876 KB |
Output is correct |
5 |
Correct |
70 ms |
12048 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
4 ms |
596 KB |
Output is correct |
8 |
Correct |
9 ms |
1492 KB |
Output is correct |
9 |
Correct |
20 ms |
3868 KB |
Output is correct |
10 |
Correct |
62 ms |
12036 KB |
Output is correct |
11 |
Correct |
1 ms |
336 KB |
Output is correct |
12 |
Correct |
2 ms |
588 KB |
Output is correct |
13 |
Correct |
7 ms |
1492 KB |
Output is correct |
14 |
Correct |
20 ms |
3796 KB |
Output is correct |
15 |
Correct |
60 ms |
12072 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
4 ms |
840 KB |
Output is correct |
19 |
Correct |
3 ms |
596 KB |
Output is correct |
20 |
Correct |
8 ms |
1568 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
3 ms |
596 KB |
Output is correct |
23 |
Correct |
11 ms |
1480 KB |
Output is correct |
24 |
Correct |
20 ms |
3776 KB |
Output is correct |
25 |
Correct |
62 ms |
11964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
596 KB |
Output is correct |
3 |
Correct |
7 ms |
1480 KB |
Output is correct |
4 |
Correct |
21 ms |
3876 KB |
Output is correct |
5 |
Correct |
70 ms |
12048 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
4 ms |
596 KB |
Output is correct |
8 |
Correct |
9 ms |
1492 KB |
Output is correct |
9 |
Correct |
20 ms |
3868 KB |
Output is correct |
10 |
Correct |
62 ms |
12036 KB |
Output is correct |
11 |
Correct |
1 ms |
336 KB |
Output is correct |
12 |
Correct |
2 ms |
588 KB |
Output is correct |
13 |
Correct |
7 ms |
1492 KB |
Output is correct |
14 |
Correct |
20 ms |
3796 KB |
Output is correct |
15 |
Correct |
60 ms |
12072 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
4 ms |
840 KB |
Output is correct |
19 |
Correct |
3 ms |
596 KB |
Output is correct |
20 |
Correct |
8 ms |
1568 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
316 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
1 ms |
324 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
3 ms |
596 KB |
Output is correct |
28 |
Correct |
11 ms |
1480 KB |
Output is correct |
29 |
Correct |
20 ms |
3776 KB |
Output is correct |
30 |
Correct |
62 ms |
11964 KB |
Output is correct |
31 |
Correct |
623 ms |
41864 KB |
Output is correct |
32 |
Correct |
73 ms |
14004 KB |
Output is correct |
33 |
Correct |
83 ms |
16620 KB |
Output is correct |
34 |
Correct |
70 ms |
13668 KB |
Output is correct |
35 |
Correct |
270 ms |
32348 KB |
Output is correct |