Submission #1051695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051695		alex_2008	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1012 ms	20308 KiB

joioi

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
using namespace std;
typedef long long ll;
const int N = 2024;
int a[N][N];
bool used[N][N];
int n, m;
int mn;
bool f(int d) {
	int mn = 1e9 + 10, mx = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (!used[i][j]) {
				mx = max(mx, a[i][j]);
				mn = min(mn, a[i][j]);
			}
		}
	}
	if ((mx - mn) <= d) return true;
	return false;
}
bool ch(int d) {
	int last_h = n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			used[i][j] = false;
		}
	}
	for (int j = m; j >= 1; j--) {
		for (int i = n; i >= n - last_h + 1; i--) {
			if (a[i][j] > (mn + d)) {
				last_h = n - i;
				break;
			}
			used[i][j] = true;
		}
	}
	if (f(d)) return true;
	last_h = n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			used[i][j] = false;
		}
	}
	for (int j = 1; j <= m; j++) {
		for (int i = n; i >= n - last_h + 1; i--) {
			if (a[i][j] > (mn + d)) {
				last_h = n - i;
				break;
			}
			used[i][j] = true;
		}
	}
	if (f(d)) return true;
	last_h = n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			used[i][j] = false;
		}
	}
	for (int j = 1; j <= m; j++) {
		for (int i = 1; i <= last_h; i++) {
			if (a[i][j] > (mn + d)) {
				last_h = i - 1;
				break;
			}
			used[i][j] = true;
		}
	}
	if (f(d)) return true;
	last_h = n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			used[i][j] = false;
		}
	}
	for (int j = m; j >= 1; j--) {
		for (int i = 1; i <= last_h; i++) {
			if (a[i][j] > (mn + d)) {
				last_h = i - 1;
				break;
			}
			used[i][j] = true;
		}
	}
	if (f(d)) return true;
	return false;
}
int main() {
	mn = 1000000010;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
			mn = min(mn, a[i][j]);
		}
	}
	int l = 0, r = 1000000010, ans = -1;
	while (l <= r) {
		int mid = (l + r) / 2;
		if (ch(mid)) {
			ans = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	cout << ans << "\n";
}

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