Submission #87853

#	Time	Username	Problem	Language	Result	Execution time	Memory
87853		KCSC	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	2643 ms	261336 KiB

joioi

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

const int DIM = 2005;

int mat[DIM][DIM];

void revLin(int n, int m) {
	for (int i = 1; i <= n / 2; ++i) {
		for (int j = 1; j <= m; ++j) {
			swap(mat[i][j], mat[n - i + 1][j]); } } }

void revCol(int n, int m) {	
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m / 2; ++j) {
			swap(mat[i][j], mat[i][m - j + 1]); } } }

bool check(int n, int m, int vl, int mn, int mx) {
	int ps = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (mat[i][j] < mx - vl) {
				ps = max(ps, j); } }
		for (int j = 1; j <= m; ++j) {
			if (mat[i][j] > mn + vl and j <= ps) {
				return false; } } }
	return true; }

int solve(int n, int m, int mn, int mx) {
	int le = 0, ri = mx - mn;
	while (le <= ri) {
		int md = (le + ri) / 2;
		if (check(n, m, md, mn, mx)) {
			ri = md - 1; }
		else {
			le = md + 1; } }
	return le; }

int main(void) {
#ifdef HOME
	freopen("joioi.in", "r", stdin); 
	freopen("joioi.out", "w", stdout);
#endif
	int n, m, mn = 1000000000, mx = 0; cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cin >> mat[i][j]; 
			mn = min(mn, mat[i][j]); mx = max(mx, mat[i][j]); } }
	int ans = 1000000000;
	ans = min(ans, solve(n, m, mn, mx)); revLin(n, m);
	ans = min(ans, solve(n, m, mn, mx)); revCol(n, m);
	ans = min(ans, solve(n, m, mn, mx)); revLin(n, m);
	ans = min(ans, solve(n, m, mn, mx)); revCol(n, m);
	cout << ans << endl;
	return 0; }

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