Submission #946212

#	Time	Username	Problem	Language	Result	Execution time	Memory
946212		Xiaoyang	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	1593 ms	111308 KiB

joioi

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define fi first 
#define se second 
#define pll pair<ll,ll>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl;
#define MP make_pair
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define SZ(x) (ll)x.size()
#define ALL(x) x.begin(),x.end()
#define endl "\n"
const ll inf=1e18;
ll lowbit(ll x){return x&(-x);}


const ll maxn=2222;
ll grid[maxn][maxn];
ll tmp[maxn][maxn];
ll n,m;
ll MIN=inf;
void rot(){
	rep(i,1,n+1){
		rep(j,1,m+1){
			tmp[j][n+1-i]=grid[i][j];
		}
	}
	swap(n,m);
	rep(i,1,n+1){
		rep(j,1,m+1){
			grid[i][j]=tmp[i][j];
		}
	}
}

bool check(ll mid){
	rep(r,0,4){
		ll lst=m,mx=0,mn=inf;
		rep(i,1,n+1){
			rep(j,1,lst+1){
				if(grid[i][j]>MIN+mid){
					lst=j-1;
					break;
				}
			}
			//the section above is always valid
			//below we just take max and min of that section and check 
			rep(j,lst+1,m+1){
				mx=max(mx,grid[i][j]);
				mn=min(mn,grid[i][j]);
			}
		}
		if(mx-mn<=mid)return 1;
		rot();
	}
	return 0;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	rep(i,1,n+1){
		rep(j,1,m+1){
			cin>>grid[i][j];
			MIN=min(MIN,grid[i][j]);
		}
	}
	
	ll lo=0,hi=1e9;
	while(lo<hi){
		ll mid=(lo+hi)>>1;
		if(check(mid))hi=mid;
		else lo=mid+1;
	}
	cout<<lo<<endl;
	return 0;
}

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