제출 #654554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
654554		Mohammad_Parsa	T-Covering (eJOI19_covering)	C++14	0 / 100	47 ms	102400 KiB

covering

/* 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=1e6+7;
int mn,t,M,ty,x[N],y[N];
vector<int> z[N],a[N],b[N],yek[N],vis[N];
int dx[4]={-2,2,0,0};
int dy[4]={0,0,-2,2};

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];
    mn=min(mn,min(a[x][y+1],min(a[x][y-1],min(a[x+1][y],a[x-1][y]))));
    b[x][y]=1,b[x-1][y]=1,b[x+1][y]=1,b[x][y-1]=1,b[x][y+1]=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);
		}
    }
}

int32_t main(){
    ios:: sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,m;
    cin>>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;
		}
	}
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    int k;
    cin>>k;
    for(int i=0;i<k;i++){
        cin>>x[i]>>y[i];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;
        }
    }

    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(n>N || m>N) return 1;
    if(f){
        cout<<"No";
        return 0;
    }
    cout<<ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 30