oj.uz

답안 #854681

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
854681 2023-09-28T13:46:58 Z willychan The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 1 ms 2392 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -