Submission #1142015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142015		nuutsnoynton	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	3836 ms	63180 KiB

joioi

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

ll a[2002][2002], b[2002][2002];
int main() {
	ll n, m,can, r, x, y, i, j, ans, t, mid, lo, hi, mn, mx;

	cin >> n >> m;
	
	mn = 1e18;
	mx = 0;
	for (i = 1; i <= n; i ++) {
		for (j = 1; j <= m; j ++) {
			cin >> a[i][j];
			mn = min(mn, a[i][j]);
			mx = max(mx, a[i][j]);
		}
	}
	
	lo = 0;
	hi = 1e9;
	//deed heseg n baga
	while ( lo < hi) {
		mid = (lo + hi)/2;
		for (i = 1; i <= n; i++) {
			for (j = 1; j <= m; j ++) {
				if ( a[i][j] - mn <= mid) b[i][j] = 1;
				else b[i][j] = 0;
			}
		}
		for (i = 1; i <= n; i ++) {
			r = 1;
			while ( r <= m && b[i][r] == 1)  r++;
			while ( r <= m) b[i][r] = 0, r ++;
		}
		for (j = 1; j <= m; j ++) {
			r = 1;
			while ( r <= n && b[r][j] == 1) r ++;
			while ( r <= n) b[r][j] = 0, r ++;
		}
		can = 1;
		for (i = 1; i <= n; i ++) {
			for (j = 1; j <= m; j ++) {
				if ( b[i][j] == 0) {
					if ( abs(mx - a[i][j]) > mid)  can  = 0;
				}
				else {
					if ( abs(mn - a[i][j]) > mid) can = 0;
				}
			}
		}
		if ( can == 0) lo = mid + 1;
		else hi = mid;
	}
	ans = lo;
		lo = 0;
	hi = ans;
	//deed heseg n baga
	while ( lo < hi) {
		mid = (lo + hi)/2;
		for (i = 1; i <= n; i++) {
			for (j = 1; j <= m; j ++) {
				if ( mx  - a[i][j] <= mid) b[i][j] = 1;
				else b[i][j] = 0;
			}
		}
		for (i = 1; i <= n; i ++) {
			r = 1;
			while ( r <= m && b[i][r] == 1)  r++;
			while ( r <= m) b[i][r] = 0, r ++;
		}
		for (j = 1; j <= m; j ++) {
			r = 1;
			while ( r <= n && b[r][j] == 1) r ++;
			while ( r <= n) b[r][j] = 0, r ++;
		}
		can = 1;
		for (i = 1; i <= n; i ++) {
			for (j = 1; j <= m; j ++) {
				if ( b[i][j] == 1) {
					if ( abs(mx - a[i][j]) > mid)  {
						can = 0;
					}
				}
				else {
					if ( abs(mn - a[i][j]) > mid) {
						can = 0;
					}
				}
			}
		}
		if ( can == 0) lo = mid + 1;
		else hi = mid;
	}
	ans = min(ans, lo);
	lo = 0;
	hi = ans;
	//deed heseg n baga
	while ( lo < hi) {
		mid = (lo + hi)/2;
		for (i = 1; i <= n; i++) {
			for (j = 1; j <= m; j ++) {
				if ( mx  - a[i][j] <= mid) b[i][j] = 1;
				else b[i][j] = 0;
			}
		}
		for (i = 1; i <= n; i ++) {
			r = m;
			while ( r >= 1 && b[i][r] == 1)  r--;
			while ( r >= 1) b[i][r] = 0, r --;
		}
		for (j = 1; j <= m; j ++) {
			r = 1;
			while ( r <= n && b[r][j] == 1) r ++;
			while ( r <= n) b[r][j] = 0, r ++;
		}
		can = 1;
		for (i = 1; i <= n; i ++) {
			for (j = 1; j <= m; j ++) {
				if ( b[i][j] == 1) {
					if ( abs(mx - a[i][j]) > mid)  {
						can = 0;
					}
				}
				else {
					if ( abs(mn - a[i][j]) > mid) {
						can = 0;
					}
				}
			}
		}
		if ( can == 0) lo = mid + 1;
		else hi = mid;
	}
	ans = min(ans, lo);
		lo = 0;
	hi = ans;
	//deed heseg n baga
	while ( lo < hi) {
		mid = (lo + hi)/2;
		for (i = 1; i <= n; i++) {
			for (j = 1; j <= m; j ++) {
				if ( a[i][j] - mn <= mid) b[i][j] = 1;
				else b[i][j] = 0;
			}
		}
		for (i = 1; i <= n; i ++) {
			r = m;
			while ( r >= 1 && b[i][r] == 1)  r--;
			while ( r >= 1) b[i][r] = 0, r --;
		}
		for (j = 1; j <= m; j ++) {
			r = 1;
			while ( r <= n && b[r][j] == 1) r ++;
			while ( r <= n) b[r][j] = 0, r ++;
		}
		can = 1;
		for (i = 1; i <= n; i ++) {
			for (j = 1; j <= m; j ++) {
				if ( b[i][j] == 0) {
					if ( abs(mx - a[i][j]) > mid)  can  = 0;
				}
				else {
					if ( abs(mn - a[i][j]) > mid) can = 0;
				}
			}
		}
		if ( can == 0) lo = mid + 1;
		else hi = mid;
	}
	ans = min(ans, lo);
	cout << ans << endl;
	
}

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