Submission #854681

#	Time	Username	Problem	Language	Result	Execution time	Memory
854681		willychan	The Kingdom of JOIOI (JOI17_joioi)	C++14	0 / 100	1 ms	2392 KiB

joioi

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds


int he[2005][2005];
int h,w;
vector<pair<int,int> > minn;

bool walked[2005][2005];
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};

int Maxn,Minn;
int cnt;
int minnn = INT_MAX;
int maxnn = INT_MIN;
int minbound[2005];
int maxbound[2005];
bool check(int d){
	for(int i=1;i<=h;i++) minbound[i]=0;
	for(int i=1;i<=h;i++) maxbound[i]=w+1;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			if(he[i][j]>minnn+d) break;
			minbound[i]=j;
		}
		for(int j=w;j>=1;j--){
			if(he[i][j]<maxnn-d) break;
			maxbound[i]=j;
		}
	}
	bool works = 1;
	for(int i=1;i<=h;i++){
		if(maxbound[i]-minbound[i]>1){works=0;break;}
	}
	if(works) return 1;
	//cout<<d<<"ok\n";
	for(int i=1;i<=h;i++) minbound[i]=w+1;
	for(int i=1;i<=h;i++) maxbound[i]=0;
	for(int i=1;i<=h;i++){
		for(int j=w;j>=1;j--){
			if(he[i][j]>minnn+d) break;
			minbound[i]=j;
		}
		for(int j=1;j<=w;j++){
			if(he[i][j]<maxnn-d) break;
			maxbound[i]=j;
		}
	}
	works = 1;
	for(int i=1;i<=h;i++){
		if(minbound[i]-maxbound[i]>1){works=0;break;}
	}
	if(works) return 1;
	return 0;
}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>h>>w;	
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			cin>>he[i][j];
			minnn = min(minnn,he[i][j]);
			maxnn = max(maxnn,he[i][j]);
		}
	}
	int l = 0;int r = 1e9+5;		
	while(r-l>1){
		int mid = (l+(r-l)/2);
//		cout<<check(mid)<<" "<<mid<<"\n";
		if(check(mid)) r = mid;
		else l = mid;
	}
	cout<<r<<"\n";
	return 0;
}

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