oj.uz

Submission #206245

# Submission time Handle Problem Language Result Execution time Memory
206245 2020-03-02T19:54:39 Z opukittpceno_hhr The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 5 ms 376 KB 
#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 c1(int l, int r) {
	auto can = [&](int i, int cnt) {
		int j = m - 1;
		int ok = 1;
		for (int c = 0; c < cnt; c++) {
			ok &= (l <= a[i][j] && a[i][j] <= r);
			j--;
		}
		return ok;
	};
	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;
	}
	// cerr << l << ' ' << r << endl;
	// for (auto t : tk) {
	// 	cerr << t << ' ';
	// }
	// cerr << endl;
	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) {
	auto can = [&](int i, int cnt) {
		int j = 0;
		int ok = 1;
		for (int c = 0; c < cnt; c++) {
			ok &= (l <= a[i][j] && a[i][j] <= r);
			j++;
		}
		return ok;
	};
	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[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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Incorrect 5 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Incorrect 5 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Incorrect 5 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -