이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |