Submission #1273152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273152		kaiboy	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	553 ms	16092 KiB

joioi

#include <algorithm>
#include <iostream>

using namespace std;

const int   N = 2000;
const int   M = 2000;
const int INF = 0x3f3f3f3f;

int aa[N][M];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, m; cin >> n >> m;
	int n_ = max(n, m), al = INF;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> aa[i][j], al = min(al, aa[i][j]);
	int ans = INF;
	for (int h = 0; h < 2; h++) {
		for (int g = 0; g < 2; g++) {
			int lower = -1, upper = INF;
			while (upper - lower > 1) {
				int d = lower + upper >> 1;
				int ar = al + d, bl = INF, br = 0;
				for (int j_ = m, i = n - 1; i >= 0; i--) {
					int j = 0;
					while (j < j_ && aa[i][j] <= ar)
						j++;
					for (j_ = j; j < m; j++) {
						bl = min(bl, aa[i][j]);
						br = max(br, aa[i][j]);
					}
				}
				if (br - bl <= d)
					upper = d;
				else
					lower = d;
			}
			ans = min(ans, upper);
			swap(n, m);
			for (int i = 0; i < n_; i++)
				for (int j = 0; j < i; j++)
					swap(aa[i][j], aa[j][i]);
		}
		for (int i = 0; i < n; i++)
			reverse(aa[i], aa[i] + m);
	}
	cout << ans << '\n';
	return 0;
}

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