Submission #849444

#	Time	Username	Problem	Language	Result	Execution time	Memory
849444		qthang2k11	The Kingdom of JOIOI (JOI17_joioi)	C++17	0 / 100	1 ms	6492 KiB

joioi

#include <bits/stdc++.h>
using namespace std;

const int N = 2003, MAX = 1e9;

int m, n, a[N][N], b[N][N], suf_max[N][N], suf_min[N][N], ans = MAX, mi = ans;

bool ok(int a[][N], int fi) {
	// cerr << fi << '\n';
	int lst = n;
	int mx = 0, l = MAX, r = 0;
	for (int i = 1; i <= m; i++) {
		int cur_lst = 0;
		for (int j = 0; j <= lst; j++) {
			cur_lst = j;
			mx = max(mx, a[i][j]);
			if (j < n && (a[i][j + 1] > fi || j == lst)) {
				l = min(l, suf_min[i][j + 1]);
				r = max(r, suf_max[i][j + 1]);
				break;
			}
		}
		lst = cur_lst;
		// fprintf(stderr, "lst[%d] = %d\n", i + 1, lst);
	}
	ans = min(ans, max({mx - mi, r - l, 0}));
	// cerr << mi << ' ' << mx << ' ' << l << ' ' << r << '\n';
	return max(mx - mi, 0) <= max(r - l, 0);
}

void deal(int a[][N]) {
	// for (int i = 1; i <= m; i++)
		// for (int j = 1; j <= n; j++)
			// cerr << a[i][j] << " \n"[j == n];
	for (int i = 1; i <= m; i++) {
		suf_max[i][n] = suf_min[i][n] = a[i][n];
		for (int j = n - 1; j > 0; j--) {
			suf_max[i][j] = max(suf_max[i][j + 1], a[i][j]);
			suf_min[i][j] = min(suf_min[i][j + 1], a[i][j]);
		}
	}
	// ok(a, 12);
	// return;
	int l = mi, r = MAX, pos = -1;
	while (l <= r) {
		int mid = (l + r) / 2;
		if (ok(a, mid)) {
			l = mid + 1;
			pos = mid;
		} else r = mid - 1;
	}
	if (pos != -1 && pos < MAX) ok(a, pos + 1);
}

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> m >> n;
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> a[i][j];
			b[m - i + 1][j] = a[i][j];
			mi = min(mi, a[i][j]);
		}
	}
	deal(a);
	deal(b);
	cout << ans;
	return 0;
}

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