제출 #73775

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
73775		KLPP	The Kingdom of JOIOI (JOI17_joioi)	C++14	60 / 100	4030 ms	103240 KiB

joioi

#include<iostream>
#include<stdio.h>

using namespace std;
int h,w;
int A[2000][2000];
int M,m;
bool test(int x){//cout<<x<<endl;
	int region[h][w];
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++)region[i][j]=-1;
	}
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if(A[i][j]>m+x){
				if(region[i][j]==-1)region[i][j]=1;
				else return false;
			}
			if(A[i][j]<M-x){
				if(region[i][j]==-1)region[i][j]=0;
				else return false;
			}//cout<<region[i][j]<<" ";
		}
	}
	/*for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			cout<<region[i][j]<<" ";
		}cout<<endl;
	}cout<<endl;*/
	int loH[h+w][2];
	int hiH[h+w][2];
	//compute hi
	for(int i=0;i<h;i++){
		hiH[i][0]=-1;
		hiH[i][1]=-1;
		for(int j=0;j<w;j++){
			if(region[i][j]==0)hiH[i][0]=j;
			if(region[i][j]==1)hiH[i][1]=j;
		}
		//cout<<hiH[i][0]<<" "<<hiH[i][1]<<endl;
	}
	//compute lo
	for(int i=0;i<h;i++){
		loH[i][0]=w;
		loH[i][1]=w;
		for(int j=w-1;j>-1;j--){
			if(region[i][j]==0)loH[i][0]=j;
			if(region[i][j]==1)loH[i][1]=j;
		}
		//cout<<loH[i][0]<<" "<<loH[i][1]<<endl;
	}
	int Hi;
	bool b;
	Hi=-1;
	b=true;
	for(int i=0;i<h;i++){
		Hi=max(Hi,hiH[i][0]);
		if(Hi>=loH[i][1])b=false;
	}
	if(b)return true;
	b=true;
	Hi=-1;
	for(int i=0;i<h;i++){
		Hi=max(Hi,hiH[i][1]);
		if(Hi>=loH[i][0])b=false;
	}
	if(b)return true;
	Hi=-1;
	b=true;
	for(int i=h-1;i>-1;i--){
		Hi=max(Hi,hiH[i][0]);
		if(Hi>=loH[i][1])b=false;
	}
	if(b)return true;
	b=true;
	Hi=-1;
	for(int i=h-1;i>-1;i--){
		Hi=max(Hi,hiH[i][1]);
		if(Hi>=loH[i][0])b=false;
	}
	if(b)return true;
	//compute hi
	for(int i=0;i<w;i++){
		hiH[i][0]=-1;
		hiH[i][1]=-1;
		for(int j=0;j<h;j++){
			if(region[j][i]==0)hiH[i][0]=j;
			if(region[j][i]==1)hiH[i][1]=j;
		}
	}
	//compute lo
	for(int i=0;i<w;i++){
		loH[i][0]=h;
		loH[i][1]=h;
		for(int j=h-1;j>-1;j--){
			if(region[j][i]==0)loH[i][0]=j;
			if(region[j][i]==1)loH[i][1]=j;
		}
	}
	Hi=-1;
	b=true;
	for(int i=0;i<w;i++){
		Hi=max(Hi,hiH[i][0]);
		if(Hi>=loH[i][1])b=false;
	}
	if(b)return true;
	b=true;
	Hi=-1;
	for(int i=0;i<w;i++){
		Hi=max(Hi,hiH[i][1]);
		if(Hi>=loH[i][0])b=false;
	}
	if(b)return true;
	Hi=-1;
	b=true;
	for(int i=w-1;i>-1;i--){
		Hi=max(Hi,hiH[i][0]);
		if(Hi>=loH[i][1])b=false;
	}
	if(b)return true;
	b=true;
	Hi=-1;
	for(int i=w-1;i>-1;i--){
		Hi=max(Hi,hiH[i][1]);
		if(Hi>=loH[i][0])b=false;
	}
	if(b)return true;
	
	return false;
}
int main(){
	cin>>h>>w;
	M=-1;
	m=1000000001;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			cin>>A[i][j];
			M=max(M,A[i][j]);
			m=min(m,A[i][j]);
		}
	}
	int hi,lo;
	lo=-1;
	hi=M-m;
	while(hi-lo>1){
		int mid=(hi+lo)/2;
		bool b=test(mid);
		if(b)hi=mid;
		else lo=mid;
	}cout<<hi<<endl;
	return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 0 / 40