# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
654593 | Mohammad_Parsa | T-Covering (eJOI19_covering) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/* in the name of allah */
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define mk make_pair
#define int long long
const int N=1e3+7;
int mn,t,M,ty,x[N*N],y[N*N];
vector<int> z[N],a[N],b[N],yek[N],vis[N];
int dx[4]={-2,2,0,0},xd[4]={-1,1,0,0};
int dy[4]={0,0,-2,2},yd[4]={0,0,-1,1};
int sumz(int x,int y){
int ans=0;
for(int i=-1;i<=1;i++)
for(int j=-1;j<=1;j++)
ans+=z[x+i][y+j];
return ans;
}
void dfs(int x,int y){
vis[x][y]=1;M++;ty+=yek[x][y];
b[x][y]=1;
for(int i=0;i<4;i++){
int p=x+dx[i],q=y+dy[i];
if(p>=0 && q>=0 && z[p][q]){
t++;
if(!vis[p][q]) dfs(p,q);
}
if(x+xd[i]>=0 && y+yd[i]>=0) mn=min(mn,a[x+xd[i]][y+yd[i]]),b[x+xd[i]][y+yd[i]]=1;
}
}
int32_t main(){
ios:: sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,m;
cin>>n>>m;
int g=0;
if(n>m) g=1,swap(n,m);
for(int i=0;i<=n+5;i++){
a[i].resize(m+5);
b[i].resize(m+5);
z[i].resize(m+5);
vis[i].resize(m+5);
yek[i].resize(m+5);
for(int j=0;j<m+5;j++){
a[i][j]=1007;
}
}
if(g) swap(n,m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(g) swap(i,j);
cin>>a[i][j];
if(g) swap(i,j);
}
}
int k;
cin>>k;
for(int i=0;i<k;i++){
cin>>x[i]>>y[i];x[i]++;y[i]++;
if(g) swap(x[i],y[i]);
z[x[i]][y[i]]=1;
}
int f=0;
for(int i=0;i<k;i++){
if((x[i]==1 && y[i]==1) || (x[i]==n && y[i]==1) || (x[i]==1 && y[i]==m) || (x[i]==n && y[i]==m)){
if(sumz(x[i],y[i])>0) f=1;
}
else if(x[i]==1 || x[i]==n || y[i]==1 || y[i]==m){
if(sumz(x[i],y[i])>1) f=1;
}
else{
if(sumz(x[i],y[i])>2) f=1;
}
}
swap(n,m);
int ans=0;
for(int i=0;i<k;i++){
int p=x[i],q=y[i];
if(p==1 || p==n || q==1 || q==m){
b[p][q]=b[p-1][q]=b[p+1][q]=b[p][q-1]=b[p][q+1]=1;
yek[p][q]=1;
}
else if(sumz(p,q)==2){
b[p][q]=b[p-1][q]=b[p+1][q]=b[p][q-1]=b[p][q+1]=1;
yek[p][q]=1;
}
}
for(int i=0;i<k;i++){
if(!vis[x[i]][y[i]]){
mn=1e9;t=0;M=0;ty=0;
dfs(x[i],y[i]);
t/=2;
//cout<<M<<" "<<t<<endl;
if(ty>1) f=1;
if(t>M) f=1;
if(t==M && ty==1) f=1;
if(t==M-1 && ty==0) ans-=mn;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ans+=b[i][j]*a[i][j];
}
}
if(n==1 || m==1) f=1;
if(f){
cout<<"No";
return 0;
}
cout<<ans;