Submission #307602

#	Time	Username	Problem	Language	Result	Execution time	Memory
307602		TeaTime	The Kingdom of JOIOI (JOI17_joioi)	C++17	0 / 100	1 ms	432 KiB

joioi

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <tuple>
#include <random>
#include <cmath>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

const ll SZ = 2010, INF = 1e9 * 1e9 + 10;

vector<ll> vec;

ll grid[SZ][SZ], pnt[SZ][SZ];

ll h, w;

vector<pair<ll, ll>> dir = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} };

bool check(ll vl) {
	for (int i = h - 1; i >= 0; i--) {
		for (int j = 0; j < w; j++) {
			pnt[i][j] = 0;
		}
	}

	ll pr = 0;
	for (int i = h - 1; i >= 0; i--) {
		ll st = pr, lst = 0;

		for (int j = pr; j < w; j++) {
			if (i < h - 1 && abs(grid[i][j] - grid[i + 1][j]) > vl) {
				lst = j + 1;
			}
		}
		for (int j = max(1ll, pr); j < w; j++) {
			if (abs(grid[i][j] - grid[i][j - 1]) > vl) {
				st = j;
				break;
			}
		}

		pr = max(lst, st);
		for (int j = max(lst, st); j < w; j++) pnt[i][j] = 1;
	}

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			for (auto cur : dir) {
				if (cur.first + i >= 0 && cur.first + i < h && cur.second + j >= 0 && cur.second + j < w) {
					ll i1 = cur.first + i, j1 = cur.second + j;
					if (pnt[i1][j1] == pnt[i][j] && abs(grid[i][j] - grid[i1][j1]) > vl) return false;
				}
			}
		}
	}

	return true;
}

int main()
{
	fastInp;

	cin >> h >> w;

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) cin >> grid[i][j];
	}
	ll l = -1, r = INF;
	while (r - l > 1) {
		ll mid = (l + r) / 2;
		if (mid == 10) {
			cout << "";
		}
		if (check(mid)) {
			r = mid;
		}
		else {
			l = mid;
		}
	}

	cout << r;

	return 0;
}
/*
4 4
1 12 6 11
11 10 2 14
10 1 9 20
4 17 19 10

8 6
23 23 10 11 16 21
15 26 19 28 19 20
25 26 28 16 15 11
11 8 19 11 15 24
14 19 15 14 24 11
10 8 11 7 6 14
23 5 19 23 17 17
18 11 21 14 20 16
*/

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