oj.uz

Submission #140843

# Submission time Handle Problem Language Result Execution time Memory
140843 2019-08-05T15:32:59 Z DrumpfTheGodEmperor The Kingdom of JOIOI (JOI17_joioi) C++14
100 / 100
 990 ms 39404 KB 
#include <bits/stdc++.h>
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s, "r", stdin);
#define out(s) freopen(s, "w", stdout);
#define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\
		freopen((string(s) + "." + end2).c_str(), "w", stdout);
#define fi first
#define se second
#define bw(i, r, l) for (int i = r - 1; i >= l; i--)
#define fw(i, l, r) for (int i = l; i < r; i++)
#define fa(i, x) for (auto i: x)
using namespace std;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4557430888798830399;
const int N = 2005;
int h, w, a[N][N], mn = inf, mni = -1, mnj = -1, mxh[N], mnLand[N], mx = -1;
bool testBoard(int direction, int x) {
	if (direction == 0) {
		if (mnLand[mnj] < mni) return false;
		//Below area contains min, upper area contains max.
		int mnInMaxLand = inf;
		fw (j, 0, w) {
			bw (i, h, mnLand[j] + 1) mnInMaxLand = min(mnInMaxLand, a[i][j]); 
		}
		if (mx - mnInMaxLand <= x) return true;
		return false;
	} else {
		if (mnLand[mnj] > mni) return false;
		int mnInMaxLand = inf;
		fw (j, 0, w) {
			fw (i, 0, mnLand[j]) mnInMaxLand = min(mnInMaxLand, a[i][j]); 
		}
		if (mx - mnInMaxLand <= x) return true;
		return false;
	}
}
bool check(int x) {
	if (mx - mn <= x) return true;
	//Fix below area as land that contains the min element.
	fw (j, 0, w) {
		mxh[j] = -1;
		fw (i, 0, h) {
			if (a[i][j] > mn + x) break;
			mxh[j] = i;
		}
	}
	if (mxh[mnj] >= mni) {
		int curMx = h - 1;
		fw (j, 0, w) {
			//Make it decreasing from left to right.
			mnLand[j] = min(curMx, mxh[j]);
			curMx = min(curMx, mxh[j]);
		}
		if (testBoard(0, x)) return true;
		curMx = h - 1;
		bw (j, w, 0) {
			//Make it decreasing from left to right.
			mnLand[j] = min(curMx, mxh[j]);
			curMx = min(curMx, mxh[j]);
		}
		if (testBoard(0, x)) return true;
	}
	//Fix above area
	fw (j, 0, w) {
		mxh[j] = h;
		bw (i, h, 0) {
			if (a[i][j] > mn + x) break;
			mxh[j] = i;
		}
	}
	if (mxh[mnj] <= mni) {
		int curMx = 0;
		fw (j, 0, w) {
			//Make it decreasing from left to right.
			mnLand[j] = max(curMx, mxh[j]);
			curMx = max(curMx, mxh[j]);
		}
		if (testBoard(1, x)) return true;
		curMx = 0;
		bw (j, w, 0) {
			//Make it decreasing from left to right.
			mnLand[j] = max(curMx, mxh[j]);
			curMx = max(curMx, mxh[j]);
		}
		if (testBoard(1, x)) return true;
	}
	return false;
}
signed main() {
	#ifdef BLU
	in("blu.inp");
	#endif
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> h >> w;
	fw (i, 0, h) fw (j, 0, w) cin >> a[i][j];
	fw (i, 0, h) fw (j, 0, w) {
		if (a[i][j] < mn) {
			mn = a[i][j];
			mni = i, mnj = j;
		}
		mx = max(mx, a[i][j]);
	}
	int l = 0, r = 1e9;
	while (l < r) {
		int m = (l + r) >> 1;
		if (check(m)) r = m;
		else l = m + 1;
	}
	cout << l;
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 5 ms 1400 KB Output is correct
17 Correct 8 ms 1528 KB Output is correct
18 Correct 8 ms 1528 KB Output is correct
19 Correct 8 ms 1528 KB Output is correct
20 Correct 7 ms 1400 KB Output is correct
21 Correct 11 ms 1656 KB Output is correct
22 Correct 9 ms 1656 KB Output is correct
23 Correct 9 ms 1656 KB Output is correct
24 Correct 9 ms 1528 KB Output is correct
25 Correct 9 ms 1656 KB Output is correct
26 Correct 11 ms 1660 KB Output is correct
27 Correct 10 ms 1656 KB Output is correct
28 Correct 10 ms 1660 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 5 ms 1400 KB Output is correct
17 Correct 8 ms 1528 KB Output is correct
18 Correct 8 ms 1528 KB Output is correct
19 Correct 8 ms 1528 KB Output is correct
20 Correct 7 ms 1400 KB Output is correct
21 Correct 11 ms 1656 KB Output is correct
22 Correct 9 ms 1656 KB Output is correct
23 Correct 9 ms 1656 KB Output is correct
24 Correct 9 ms 1528 KB Output is correct
25 Correct 9 ms 1656 KB Output is correct
26 Correct 11 ms 1660 KB Output is correct
27 Correct 10 ms 1656 KB Output is correct
28 Correct 10 ms 1660 KB Output is correct
29 Correct 573 ms 37368 KB Output is correct
30 Correct 562 ms 37780 KB Output is correct
31 Correct 593 ms 39260 KB Output is correct
32 Correct 585 ms 39404 KB Output is correct
33 Correct 487 ms 34064 KB Output is correct
34 Correct 576 ms 26460 KB Output is correct
35 Correct 990 ms 28960 KB Output is correct
36 Correct 846 ms 33272 KB Output is correct
37 Correct 964 ms 29236 KB Output is correct