Submission #1199436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199436		Saul0906	The Kingdom of JOIOI (JOI17_joioi)	C++20	60 / 100	4094 ms	74752 KiB

joioi

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repr(a,b,c) for(int a=b-1; a>c-1; a--)
#define repa(a,b) for(auto a:b)
#define mid ((l+r)>>1)
#define endl "\n"

using namespace std;

using vi = vector<int>;

const int N=2005, inf=1e9+5;

int h, w, g[N][N], pf[N][N][2][2], ans;

void solve(int x, int y, int a, int b, int mn, int mn2){
	int z;
	if(x==0) z=1;
	else z=-1;
	int mx=0, lst;
	if(y) lst=0;
	else lst=w;
	rep(i,0,h){
		int l=0, r=w-1;
		while(l<=r){
			if(!y){
				if(pf[x][mid][0][0]>=mn) l=mid+1;
				else r=mid-1;
			}else{
				if(pf[x][mid][1][0]>=mn) r=mid-1;
				else l=mid+1;
			}
		}
		if(!y){
			l=min(l,lst);
			r=l-1;
			if(x==a && b>=l) return;
			mx=max({mx,pf[x][r][0][1]-mn,pf[x][l][1][1]-mn2});
		}else{
			l=max(l,lst);
			r=l-1;
			if(x==a && b<=r) return;
			mx=max({mx,pf[x][l][1][1]-mn,pf[x][r][0][1]-mn2});
		}
		x+=z;
		lst=l;
	}
	ans=min(ans,mx);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>h>>w;
	int mn=inf, mx=-inf, x, y;
	rep(i,0,h) rep(j,0,w){
		cin>>g[i][j];
		mn=min(mn,g[i][j]);
		mx=max(mx,g[i][j]);
	}
	ans=mx-mn;
	rep(i,0,h){
		x=inf;
		y=-inf;
		rep(j,0,w) x=min(x,g[i][j]), y=max(y,g[i][j]), pf[i][j][0][0]=x, pf[i][j][0][1]=y;
		x=inf;
		y=-inf;
		repr(j,w,0) x=min(x,g[i][j]), y=max(y,g[i][j]), pf[i][j][1][0]=x, pf[i][j][1][1]=y;
	}
	rep(i,0,h) rep(j,0,w){
		if(g[i][j]==mn) continue;
		solve(0,0,i,j,g[i][j],mn);
		solve(0,w-1,i,j,g[i][j],mn);
		solve(h-1,0,i,j,g[i][j],mn);
		solve(h-1,w-1,i,j,g[i][j],mn);
	}
	cout<<ans<<endl;
}

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