oj.uz

Submission #387247

# Submission time Handle Problem Language Result Execution time Memory
387247 2021-04-08T07:31:18 Z Trunkty The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 1 ms 364 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -