Submission #206247

#	Time	Username	Problem	Language	Result	Execution time	Memory
206247		opukittpceno_hhr	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	1983 ms	31864 KiB

joioi

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <random>

using namespace std;

const int N = 2001;
const int INF = 1e9 + 239;

int n, m;
int a[N][N];
int cn[N][N];

int c1(int l, int r) {
	{
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cn[i][j] = 0;
			}
		}
		for (int i = 0; i < n; i++) {
			cn[i][0] = 1;
			int ok = 1;
			int j = m - 1;
			for (int c = 1; c <= m; c++) {
				ok &= (l <= a[i][j] && a[i][j] <= r);
				j--;
				cn[i][c] = ok;
			}
		}
	}
	auto can = [&](int i, int cnt) {
		return cn[i][cnt];
	};
	vector<int> tk(n);
	int pnt = 0;
	for (int cnt = 0; cnt <= m; cnt++) {
		if (can(n - 1, cnt)) {
			pnt = cnt;
		}
	}
	if (pnt == 0) return false;
	tk[n - 1] = pnt;
	for (int i = n - 2; i >= 0; i--) {
		while (!can(i, pnt)) {
			pnt--;
		}
		tk[i] = pnt;
	}
	int cmax = -1;
	int cmin = INF;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m - tk[i]; j++) {
			cmax = max(cmax, a[i][j]);
			cmin = min(cmin, a[i][j]);
		}
	}
	return cmax - cmin <= r - l;
}

int c2(int l, int r) {
	{
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cn[i][j] = 0;
			}
		}
		for (int i = 0; i < n; i++) {
			cn[i][0] = 1;
			int ok = 1;
			int j = 0;
			for (int c = 1; c <= m; c++) {
				ok &= (l <= a[i][j] && a[i][j] <= r);
				j++;
				cn[i][c] = ok;
			}
		}
	}
	auto can = [&](int i, int cnt) {
		return cn[i][cnt];
	};
	vector<int> tk(n);
	int pnt = 0;
	for (int cnt = 0; cnt <= m; cnt++) {
		if (can(0, cnt)) {
			pnt = cnt;
		}
	}
	if (pnt == 0) return false;
	tk[0] = pnt;
	for (int i = 1; i < n; i++) {
		while (!can(i, pnt)) {
			pnt--;
		}
		tk[i] = pnt;
	}
	int cmax = -1;
	int cmin = INF;
	for (int i = 0; i < n; i++) {
		for (int j = tk[i]; j < m; j++) {
			cmax = max(cmax, a[i][j]);
			cmin = min(cmin, a[i][j]);
		}
	}
	return cmax - cmin <= r - l;
}

int solve() {
	int r = -1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			r = max(r, a[i][j]);
		}
	}
	auto check = [&](int x) {
		return c1(r - x, r) || c2(r - x, r);
	};
	int tl = -1;
	int tr = INF;
	while (tr - tl > 1) {
		int tm = (tl + tr) / 2;
		if (check(tm)) tr = tm;
		else tl = tm;
	}
	return tr;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}
	int ans = solve();
	for (int i = 0; i < n; i++) {
		reverse(a[i], a[i] + m);
	}
	ans = min(ans, solve());
	cout << ans << endl;
}

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