Submission #143072

#	Time	Username	Problem	Language	Result	Execution time	Memory
143072		godwind	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1374 ms	54976 KiB

joioi

#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
                        
using namespace std;
                        
template<typename T> void uin(T &a, T b) {
    if (b < a) {
        a = b;
    }
}
                        
template<typename T> void uax(T &a, T b) {
    if (b > a) {
        a = b;
    }
}

#define ghost signed
#define left left228
#define right right228
#define complex complex228
#define count count228
#define sin sin228
#define list list228

const int N = 2003;
const int INF = 1e9 + 228;

int res = INF;
int n, m;
int a[N][N];
int left[N], right[N];
int mn = INF, mx = 0;

void solve() {
	int l = -1, r = mx - mn;
	while (r - l > 1) {
		int mid = (l + r) >> 1;
		int x = mid;
		for (int i = 1; i <= n; ++i) {
			left[i] = 0, right[i] = m + 1;
			for (int j = 1; j <= m; ++j) {
				if (a[i][j] > mn + x && right[i] == m + 1) right[i] = j - 1;
				if (a[i][j] < mx - x) left[i] = j;
			}
		}
		bool OK1 = 1, OK2 = 1;
		int last1 = left[1], last2 = right[1];
		if (left[1] > right[1]) OK1 = OK2 = 0;
		for (int i = 2; i <= n; ++i) {
			if (max(last1, left[i]) > right[i]) OK1 = 0;
			uax(last1, left[i]);
			if (min(last2, right[i]) < left[i]) OK2 = 0;
			uin(last2, right[i]);
		}
		if (OK1 || OK2) r = mid;
		else l = mid;
	}
	uin(res, r);
}

ghost main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cin >> a[i][j];
			uax(mx, a[i][j]);
			uin(mn, a[i][j]);
		}
	}
	res = mx - mn;
	solve();
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m / 2; ++j) {
			swap(a[i][j], a[i][m - j + 1]);
		}
	}
	solve();
	cout << res << '\n';
    return 0;
} // kek ;
// Ого! Кажетсья это $#@!
 

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