Submission #647174

#	Time	Username	Problem	Language	Result	Execution time	Memory
647174		beaconmc	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	2207 ms	164456 KiB

joioi

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)

#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)

ll n,m;
ll grid[2001][2001];
ll grid2[2001][2001];

ll mx = -1;

ll minmaxl[2001][2001];
ll minmaxr[2001][2001];

void setup(){

	FORNEG(i,n-1,-1){
		minmaxl[i][0] = grid[i][0];
		FOR(j,1,m){
			minmaxl[i][j] = min(minmaxl[i][j-1], grid[i][j]);
		}
		if (i!=n-1){
			FOR(j,0,m){
				minmaxl[i][j] = min(minmaxl[i][j], minmaxl[i+1][j]);
			}
		}
	}

	FORNEG(i,n-1,-1){
		minmaxr[i][m-1] = grid[i][m-1];
		FORNEG(j,m-2,-1){
			minmaxr[i][j] = min(minmaxr[i][j+1], grid[i][j]);
		}
		if (i != n-1){
			FORNEG(j,m-1,-1){
				minmaxr[i][j] = min(minmaxr[i][j], minmaxr[i+1][j]);
			}
		}
	}
}

bool check(ll a){
	ll mini = 1000000000;
	ll maxi = -1;

	FOR(i,0,n){
		FOR(j,0,m){
			if (mx-minmaxl[i][j] > a){
            	mini = min(mini, grid[i][j]);
            	maxi = max(maxi, grid[i][j]);
			}
		}
	}

	if (maxi - mini <= a) return true;

	mini = 1000000000;
	maxi = -1;
	FOR(i,0,n){
		FOR(j,0,m){
			if (mx-minmaxr[i][j] > a){
            	mini = min(mini, grid[i][j]);
            	maxi = max(maxi, grid[i][j]);
			}
		}
	}

	if (maxi - mini <= a) return true;
	return false;

}
int main(){
	cin >> n >> m;
	FOR(i,0,n){
		FOR(j,0,m){
			cin >> grid[i][j];
			mx = max(mx, grid[i][j]);
			grid2[n-i-1][m-j-1] = grid[i][j];
		}
	}
	FOR(i,0,n){
		FOR(j,0,m){
			minmaxl[i][j] = 1000000000;
			minmaxr[i][j] = 1000000000;
		}
	}

	setup();

	ll lo = 0;
	ll hi = mx;
	while (lo<hi){
		ll mid = (lo+hi)/2;
		if (check(mid)){
			hi = mid;
		}
		else{
			lo = mid+1;
		}
	}

	ll ans = lo;

	FOR(i,0,n) FOR(j,0,m) grid[i][j] = grid2[i][j];

	FOR(i,0,n){
		FOR(j,0,m){
			minmaxl[i][j] = 1000000000;
			minmaxr[i][j] = 1000000000;
		}
	}



	setup();
	lo = 0;
	hi = mx;
	while (lo<hi){
		ll mid = (lo+hi)/2;
		if (check(mid)){
			hi = mid;
		}
		else{
			lo = mid+1;
		}
	}

	cout << min(ans,lo);



}

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