Submission #387247

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

joioi

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int h,w,maxi;
int grid[2005][2005];
int hasmax[2005][3];

bool check(int a){
	bool yes=true;
	int minl=w,maxo=0,mino=1e9;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=minl;j++){
			if(maxi-grid[i][j]>a){
				minl = j-1;
				break;
			}
		}
		for(int j=minl;j<=w;j++){
			mino = min(mino,grid[i][j]);
			maxo = max(maxo,grid[i][j]);
		}
		if(minl<hasmax[i][2] or maxo-mino>a){
			yes = false;
			break;
		}
	}
	if(yes){
		return true;
	}
	yes=true;
	minl=w,maxo=0,mino=1e9;
	for(int i=h;i>=1;i--){
		for(int j=1;j<=minl;j++){
			if(maxi-grid[i][j]>a){
				minl = j-1;
				break;
			}
		}
		for(int j=minl;j<=w;j++){
			mino = min(mino,grid[i][j]);
			maxo = max(maxo,grid[i][j]);
		}
		if(minl<hasmax[i][2] or maxo-mino>a){
			yes = false;
			break;
		}
	}
	if(yes){
		return true;
	}
	yes=true;
	minl=1,maxo=0,mino=1e9;
	for(int i=1;i<=h;i++){
		for(int j=w;j>=minl;j--){
			if(maxi-grid[i][j]>a){
				minl = j+1;
				break;
			}
		}
		for(int j=1;j<minl;j++){
			mino = min(mino,grid[i][j]);
			maxo = max(maxo,grid[i][j]);
		}
		if(minl>hasmax[i][1] or maxo-mino>a){
			yes = false;
			break;
		}
	}
	if(yes){
		return true;
	}
	yes=true;
	minl=1,maxo=0,mino=1e9;
	for(int i=h;i>=1;i--){
		for(int j=w;j>=minl;j--){
			if(maxi-grid[i][j]>a){
				minl = j+1;
				break;
			}
		}
		for(int j=1;j<minl;j++){
			mino = min(mino,grid[i][j]);
			maxo = max(maxo,grid[i][j]);
		}
		if(minl>hasmax[i][1] or maxo-mino>a){
			yes = false;
			break;
		}
	}
	if(yes){
		return true;
	}
	return false;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> h >> w;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			cin >> grid[i][j];
			maxi = max(maxi,grid[i][j]);
		}
	}
	for(int i=1;i<=h;i++){
		hasmax[i][1] = 1e9;
		for(int j=1;j<=w;j++){
			if(grid[i][j]==maxi){
				hasmax[i][1] = min(hasmax[i][1],j);
				hasmax[i][2] = j;
			}
		}
	}
	int low=0,high=maxi-1,mid;
	while(low!=high){
		mid = (low+high-(low+high)%2)/2;
		if(check(mid)){
			high = mid;
		}
		else{
			low = mid+1;
		}
	}
	
	cout << low;
	
	return 0;
}

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