Submission #1281147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281147		third	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	472 ms	94840 KiB

joioi

#include<bits/stdc++.h>
typedef long long ll;
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl '\n'
#define TASK ""
#define N 2005
#define LOG 17
using namespace std;

const ll inf = 2e9;

bool ghuy4g;

const ll hx[] = {1, -1, 0, 0};
const ll hy[] = {0, 0, 1, -1};

ll h, w, a[N][N], b[N][N], par[N * N], sz[N * N], val, den[N];
bool vst[N][N];

pii mxx;

vector<ll> ns;

/////
///
///
//
//

bool check1(ll mid) {
	ll prev = w;
	for (int i = 1; i <= mxx.fi; i ++) {
		for (int j = 1; j <= mxx.se; j ++) {
			if (val - a[i][j] > mid) return 0;
			den[i] = j;
		}
		ll j = mxx.se + 1;
		while (j <= prev && val - a[i][j] <= mid) {
			den[i] = j;
			j ++ ;
		}
		prev = den[i];
	}
	for (int i = mxx.fi + 1; i <= h; i ++) {
		ll j = 1;
		den[i] = 0;
		while (j <= prev && val - a[i][j] <= mid) {
			den[i] = j;
			j ++ ;
		}
		prev = den[i];
	}
	ll cmax = -inf, cmin = inf;
	for (int i = 1; i <= h; i ++) {
		for (int j = den[i] + 1; j <= w; j ++) {
			cmax = max(cmax, a[i][j]);
			cmin = min(cmin, a[i][j]);
		}
	}
	if (cmax - cmin > mid) return 0;
	return 1;
}

//
////
////
////
/////
//////

bool check2(ll mid) {
	ll prev = w;
	for (int i = h; i >= mxx.fi; i --) {
		for (int j = 1; j <= mxx.se; j ++) {
			if (val - a[i][j] > mid) return 0;
			den[i] = j;
		}
		ll j = mxx.se + 1;
		while (j <= prev && val - a[i][j] <= mid) {
			den[i] = j;
			j ++ ;
		}
		prev = den[i];
	}
	for (int i = mxx.fi - 1; i >= 1; i --) {
		ll j = 1;
		den[i] = 0;
		while (j <= prev && val - a[i][j] <= mid) {
			den[i] = j;
			j ++ ;
		}
		prev = den[i];
	}
	ll cmax = -inf, cmin = inf;
	for (int i = 1; i <= h; i ++) {
		for (int j = den[i] + 1; j <= w; j ++) {
			cmax = max(cmax, a[i][j]);
			cmin = min(cmin, a[i][j]);
		}
	}
	if (cmax - cmin > mid) return 0;
	return 1;
}

void solve() {
	ll ans1 = inf;
	ll l = 1, r = 1e9, ans = -1;
	while (l <= r) {
		ll mid = (l + r) / 2;
		if (check1(mid) || check2(mid)) {
			ans = mid;
			r = mid - 1;
		}
		else {
			l = mid + 1;
		}
	}
	if (ans != -1) {
		ans1 = min(ans1, ans);
	}
	
	for (int i = 1; i <= h; i ++) {
		for (int j = 1; j <= w; j ++) {
			a[i][j] = b[i][w - j + 1];
		}
	}
	
	for (int i = 1; i <= h; i ++) {
		for (int j = 1; j <= w; j ++) {
			if (a[i][j] > a[mxx.fi][mxx.se]) {
   				mxx = {i, j};
   			}
			//cout << a[i][j] << " ";
		}
		//cout << endl;
	}
	
	l = 1, r = 1e9, ans = -1;
	while (l <= r) {
		ll mid = (l + r) / 2;
		//cout << mid << " " << check1(mid) << " " << check2(mid) << endl;
		if (check1(mid) || check2(mid)) {
			ans = mid;
			r = mid - 1;
		}
		else {
			l = mid + 1;
		}
	}
	//cout << check2(11) << endl;
	if (ans != -1) {
		ans1 = min(ans1, ans);
	}
	cout << ans1 << endl;
}

bool klinh;

signed main() {
   // freopen("test.inp", "r", stdin);
	//freopen("test.out", "w", stdout);
	//srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
   	cin >> h >> w;
   	//cout << get(6).fi << " " << get(6).se << endl;
   	for (int i = 1; i <= h; i ++) {
   		for (int j = 1; j <= w; j ++) {
   			cin >> a[i][j];
   			b[i][j] = a[i][j];
   			val = max(val, a[i][j]);
   			if (a[i][j] > a[mxx.fi][mxx.se]) {
   				mxx = {i, j};
   			}
   			ns.push_back(a[i][j]);
   		}
   	}
   	   	
   	solve();
   	
   	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
}

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