oj.uz

Submission #206247

# Submission time Handle Problem Language Result Execution time Memory
206247 2020-03-02T19:59:55 Z opukittpceno_hhr The Kingdom of JOIOI (JOI17_joioi) C++17
100 / 100
 1983 ms 31864 KB 
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <random>

using namespace std;

const int N = 2001;
const int INF = 1e9 + 239;

int n, m;
int a[N][N];
int cn[N][N];

int c1(int l, int r) {
	{
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cn[i][j] = 0;
			}
		}
		for (int i = 0; i < n; i++) {
			cn[i][0] = 1;
			int ok = 1;
			int j = m - 1;
			for (int c = 1; c <= m; c++) {
				ok &= (l <= a[i][j] && a[i][j] <= r);
				j--;
				cn[i][c] = ok;
			}
		}
	}
	auto can = [&](int i, int cnt) {
		return cn[i][cnt];
	};
	vector<int> tk(n);
	int pnt = 0;
	for (int cnt = 0; cnt <= m; cnt++) {
		if (can(n - 1, cnt)) {
			pnt = cnt;
		}
	}
	if (pnt == 0) return false;
	tk[n - 1] = pnt;
	for (int i = n - 2; i >= 0; i--) {
		while (!can(i, pnt)) {
			pnt--;
		}
		tk[i] = pnt;
	}
	int cmax = -1;
	int cmin = INF;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m - tk[i]; j++) {
			cmax = max(cmax, a[i][j]);
			cmin = min(cmin, a[i][j]);
		}
	}
	return cmax - cmin <= r - l;
}

int c2(int l, int r) {
	{
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cn[i][j] = 0;
			}
		}
		for (int i = 0; i < n; i++) {
			cn[i][0] = 1;
			int ok = 1;
			int j = 0;
			for (int c = 1; c <= m; c++) {
				ok &= (l <= a[i][j] && a[i][j] <= r);
				j++;
				cn[i][c] = ok;
			}
		}
	}
	auto can = [&](int i, int cnt) {
		return cn[i][cnt];
	};
	vector<int> tk(n);
	int pnt = 0;
	for (int cnt = 0; cnt <= m; cnt++) {
		if (can(0, cnt)) {
			pnt = cnt;
		}
	}
	if (pnt == 0) return false;
	tk[0] = pnt;
	for (int i = 1; i < n; i++) {
		while (!can(i, pnt)) {
			pnt--;
		}
		tk[i] = pnt;
	}
	int cmax = -1;
	int cmin = INF;
	for (int i = 0; i < n; i++) {
		for (int j = tk[i]; j < m; j++) {
			cmax = max(cmax, a[i][j]);
			cmin = min(cmin, a[i][j]);
		}
	}
	return cmax - cmin <= r - l;
}

int solve() {
	int r = -1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			r = max(r, a[i][j]);
		}
	}
	auto check = [&](int x) {
		return c1(r - x, r) || c2(r - x, r);
	};
	int tl = -1;
	int tr = INF;
	while (tr - tl > 1) {
		int tm = (tl + tr) / 2;
		if (check(tm)) tr = tm;
		else tl = tm;
	}
	return tr;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}
	int ans = solve();
	for (int i = 0; i < n; i++) {
		reverse(a[i], a[i] + m);
	}
	ans = min(ans, solve());
	cout << ans << endl;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 15992 KB Output is correct
2 Correct 171 ms 16120 KB Output is correct
3 Correct 243 ms 16092 KB Output is correct
4 Correct 268 ms 16120 KB Output is correct
5 Correct 221 ms 15992 KB Output is correct
6 Correct 265 ms 15992 KB Output is correct
7 Correct 274 ms 16120 KB Output is correct
8 Correct 280 ms 15992 KB Output is correct
9 Correct 301 ms 15996 KB Output is correct
10 Correct 290 ms 16124 KB Output is correct
11 Correct 262 ms 15992 KB Output is correct
12 Correct 279 ms 15992 KB Output is correct
13 Correct 296 ms 16096 KB Output is correct
14 Correct 281 ms 15992 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 15992 KB Output is correct
2 Correct 171 ms 16120 KB Output is correct
3 Correct 243 ms 16092 KB Output is correct
4 Correct 268 ms 16120 KB Output is correct
5 Correct 221 ms 15992 KB Output is correct
6 Correct 265 ms 15992 KB Output is correct
7 Correct 274 ms 16120 KB Output is correct
8 Correct 280 ms 15992 KB Output is correct
9 Correct 301 ms 15996 KB Output is correct
10 Correct 290 ms 16124 KB Output is correct
11 Correct 262 ms 15992 KB Output is correct
12 Correct 279 ms 15992 KB Output is correct
13 Correct 296 ms 16096 KB Output is correct
14 Correct 281 ms 15992 KB Output is correct
15 Correct 174 ms 16120 KB Output is correct
16 Correct 189 ms 17016 KB Output is correct
17 Correct 225 ms 17016 KB Output is correct
18 Correct 236 ms 17144 KB Output is correct
19 Correct 253 ms 17016 KB Output is correct
20 Correct 244 ms 16892 KB Output is correct
21 Correct 298 ms 17144 KB Output is correct
22 Correct 329 ms 17016 KB Output is correct
23 Correct 248 ms 17032 KB Output is correct
24 Correct 285 ms 17016 KB Output is correct
25 Correct 254 ms 17016 KB Output is correct
26 Correct 333 ms 17032 KB Output is correct
27 Correct 288 ms 17016 KB Output is correct
28 Correct 325 ms 17144 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 15992 KB Output is correct
2 Correct 171 ms 16120 KB Output is correct
3 Correct 243 ms 16092 KB Output is correct
4 Correct 268 ms 16120 KB Output is correct
5 Correct 221 ms 15992 KB Output is correct
6 Correct 265 ms 15992 KB Output is correct
7 Correct 274 ms 16120 KB Output is correct
8 Correct 280 ms 15992 KB Output is correct
9 Correct 301 ms 15996 KB Output is correct
10 Correct 290 ms 16124 KB Output is correct
11 Correct 262 ms 15992 KB Output is correct
12 Correct 279 ms 15992 KB Output is correct
13 Correct 296 ms 16096 KB Output is correct
14 Correct 281 ms 15992 KB Output is correct
15 Correct 174 ms 16120 KB Output is correct
16 Correct 189 ms 17016 KB Output is correct
17 Correct 225 ms 17016 KB Output is correct
18 Correct 236 ms 17144 KB Output is correct
19 Correct 253 ms 17016 KB Output is correct
20 Correct 244 ms 16892 KB Output is correct
21 Correct 298 ms 17144 KB Output is correct
22 Correct 329 ms 17016 KB Output is correct
23 Correct 248 ms 17032 KB Output is correct
24 Correct 285 ms 17016 KB Output is correct
25 Correct 254 ms 17016 KB Output is correct
26 Correct 333 ms 17032 KB Output is correct
27 Correct 288 ms 17016 KB Output is correct
28 Correct 325 ms 17144 KB Output is correct
29 Correct 1271 ms 30968 KB Output is correct
30 Correct 1314 ms 31740 KB Output is correct
31 Correct 1367 ms 31832 KB Output is correct
32 Correct 1361 ms 31736 KB Output is correct
33 Correct 1126 ms 29788 KB Output is correct
34 Correct 1393 ms 31736 KB Output is correct
35 Correct 1983 ms 31864 KB Output is correct
36 Correct 1612 ms 31760 KB Output is correct
37 Correct 1872 ms 31736 KB Output is correct