Submission #489113

#	Time	Username	Problem	Language	Result	Execution time	Memory
489113		cheissmart	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	2001 ms	70840 KiB

joioi

#include <bits/stdc++.h>
#define IO_OP ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emaplce_back
#define MP make_pair
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;

const int INF = 1e9 + 7, N = 2003;

int a[N][N];

signed main()
{
	IO_OP;

	int h, w;
	cin >> h >> w;
	int mx = 0, mn = INF;
	for(int i = 0; i < h; i++) {
		for(int j = 0; j < w; j++) {
			cin >> a[i][j];
			mx = max(mx, a[i][j]);
			mn = min(mn, a[i][j]);
		}
	}
	
	auto ok = [&] (int max_ans) {
		auto must_with_mx = [&] (int x) {
			return x - mn > max_ans;	
		};
		auto must_with_mn = [&] (int x) {
			return mx - x > max_ans;	
		};
		auto yes1 = [&]() {
			V<vi> b(h, vi(w));
			for(int i = 0; i < h; i++) 
				for(int j = 0; j < w; j++)
					if(must_with_mx(a[i][j]))
						b[i][j] = 1;
			for(int i = 0; i < h; i++)
				for(int j = w - 1; j >= 0; j--) {
					if(i + 1 < h) b[i + 1][j] |= b[i][j];
					if(j - 1 >= 0) b[i][j - 1] |= b[i][j];
					if(b[i][j] && must_with_mn(a[i][j]))
						return false;
				}
			return true;			
		};
		
		auto yes2 = [&]() {
			V<vi> b(h, vi(w));
			for(int i = 0; i < h; i++)
				for(int j = 0; j < w; j++)
					if(must_with_mx(a[i][j]))
						b[i][j] = 1;
			for(int i = h - 1; i >= 0; i--)
				for(int j = w - 1; j >= 0; j--) {
					if(i - 1 >= 0) b[i - 1][j] |= b[i][j];
					if(j - 1 >= 0) b[i][j - 1] |= b[i][j];
					if(b[i][j] && must_with_mn(a[i][j]))
						return false;
				}
			return true;			
		};
		auto yes3 = [&]() {
			V<vi> b(h, vi(w));
			for(int i = 0; i < h; i++) 
				for(int j = 0; j < w; j++)
					if(must_with_mn(a[i][j]))
						b[i][j] = 1;
			for(int i = 0; i < h; i++)
				for(int j = w - 1; j >= 0; j--) {
					if(i + 1 < h) b[i + 1][j] |= b[i][j];
					if(j - 1 >= 0) b[i][j - 1] |= b[i][j];
					if(b[i][j] && must_with_mx(a[i][j]))
						return false;
				}
			return true;			
		};
		
		auto yes4 = [&]() {
			V<vi> b(h, vi(w));
			for(int i = 0; i < h; i++)
				for(int j = 0; j < w; j++)
					if(must_with_mn(a[i][j]))
						b[i][j] = 1;
			for(int i = h - 1; i >= 0; i--)
				for(int j = w - 1; j >= 0; j--) {
					if(i - 1 >= 0) b[i - 1][j] |= b[i][j];
					if(j - 1 >= 0) b[i][j - 1] |= b[i][j];
					if(b[i][j] && must_with_mx(a[i][j]))
						return false;
				}
			return true;			
		};
		return yes1() || yes2() || yes3() || yes4();
	};
	
	int lb = 0, rb = mx - mn - 1;
	while(lb <= rb) {
		int mb = (lb + rb) / 2;
		if(ok(mb))
			rb = mb - 1;
		else
			lb = mb + 1;
	}
	cout << lb << '\n';
		
}

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