Submission #365481

#	Time	Username	Problem	Language	Result	Execution time	Memory
365481		inluminas	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	775 ms	19948 KiB

joioi

#include"bits/stdc++.h"
using namespace std;

#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)

const int lmt=2e3+3;
int a[lmt][lmt],h,w,mx,mn=INT_MAX;



bool ok(int dif){
	int last=w;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=last;j++){
			if(abs(mx-a[i][j])>dif){
				last=j-1;
				break;
			}
		}
		for(int j=last+1;j<=w;j++){
			if(abs(mn-a[i][j])>dif){
				return false;
			}
		}
	}
	return true;
}

int bs(){
	int lo=0,hi=mx-mn;
	while(hi-lo>1){
		int mid=(lo+hi)/2;
		if(ok(mid)){
			hi=mid;
		}else{
			lo=mid;
		}
	}
	if(ok(lo)) return lo;
	else return hi;
}

int main(){
	fastio;

	cin>>h>>w;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			cin>>a[i][j];
			mn=min(mn,a[i][j]),mx=max(mx,a[i][j]);
		}
	}
	int ans=bs();
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w/2;j++){
			swap(a[i][j],a[i][w-j+1]);
		}
	}
	ans=min(ans,bs());
	for(int i=1;i<=h/2;i++){
		for(int j=1;j<=w;j++){
			swap(a[i][j],a[h-i+1][j]);
		}
	}
	ans=min(ans,bs());
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w/2;j++){
			swap(a[i][j],a[i][w-j+1]);
		}
	}
	ans=min(ans,bs());
	cout<<ans<<endl;
	return 0;
}

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