Submission #902544

#	Time	Username	Problem	Language	Result	Execution time	Memory
902544		LCJLY	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1432 ms	165112 KiB

joioi

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl; 
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<long long,long long>pii;

int n,m;
int arr[2005][2005];
int arr2[2005][2005]; 
int arr3[2005][2005];
int arr4[2005][2005];
int mini=INT_MAX;
int maxi=0;

bool check(int range){
	int l=mini+range;
	int r=maxi-range;
	
	int ptr=-1;
	int ptr2=-1;
	int ptr3=-1;
	int ptr4=-1;
	
	bool amos=true;
	bool amos2=true;
	bool amos3=true;
	bool amos4=true;
	
	for(int x=0;x<n;x++){
		for(int y=0;y<m;y++){
			if(arr[x][y]>l) ptr=max(ptr,y);
			if(arr2[x][y]>l) ptr2=max(ptr2,y);
			if(arr3[x][y]>l) ptr3=max(ptr3,y);
			if(arr4[x][y]>l) ptr4=max(ptr4,y);
		}
		
		for(int y=0;y<=ptr;y++){
			if(arr[x][y]<r)  amos=false;
		}
		
		for(int y=0;y<=ptr2;y++){
			if(arr2[x][y]<r)  amos2=false;
		}
		
		for(int y=0;y<=ptr3;y++){
			if(arr3[x][y]<r)  amos3=false;
		}
		
		for(int y=0;y<=ptr4;y++){
			if(arr4[x][y]<r)  amos4=false;
		}
	}
	
	return amos|amos2|amos3|amos4;
}


void solve(){	
	cin >> n >> m;
	
	for(int x=0;x<n;x++){
		for(int y=0;y<m;y++){
			cin >> arr[x][y];
			mini=min(mini,arr[x][y]);
			maxi=max(maxi,arr[x][y]);
		}
	}
	
	for(int x=0;x<n;x++){
		for(int y=0;y<m;y++){
			arr2[x][y]=arr[n-x-1][m-y-1];
			arr3[x][y]=arr[n-x-1][y];
			arr4[x][y]=arr[x][m-y-1];
		}
	}
	
	int l=0;
	int r=1e9;
	int best=r;
	int mid;
	
	while(l<=r){
		mid=(l+r)/2;
		if(check(mid)){
			best=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	
	cout << best;
}	
 
int32_t main(){										
	ios::sync_with_stdio(0);	
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}


 

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