Submission #1051695

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1051695	2024-08-10T09:05:45 Z	alex_2008	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1012 ms	20308 KB

joioi

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
using namespace std;
typedef long long ll;
const int N = 2024;
int a[N][N];
bool used[N][N];
int n, m;
int mn;
bool f(int d) {
	int mn = 1e9 + 10, mx = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (!used[i][j]) {
				mx = max(mx, a[i][j]);
				mn = min(mn, a[i][j]);
			}
		}
	}
	if ((mx - mn) <= d) return true;
	return false;
}
bool ch(int d) {
	int last_h = n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			used[i][j] = false;
		}
	}
	for (int j = m; j >= 1; j--) {
		for (int i = n; i >= n - last_h + 1; i--) {
			if (a[i][j] > (mn + d)) {
				last_h = n - i;
				break;
			}
			used[i][j] = true;
		}
	}
	if (f(d)) return true;
	last_h = n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			used[i][j] = false;
		}
	}
	for (int j = 1; j <= m; j++) {
		for (int i = n; i >= n - last_h + 1; i--) {
			if (a[i][j] > (mn + d)) {
				last_h = n - i;
				break;
			}
			used[i][j] = true;
		}
	}
	if (f(d)) return true;
	last_h = n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			used[i][j] = false;
		}
	}
	for (int j = 1; j <= m; j++) {
		for (int i = 1; i <= last_h; i++) {
			if (a[i][j] > (mn + d)) {
				last_h = i - 1;
				break;
			}
			used[i][j] = true;
		}
	}
	if (f(d)) return true;
	last_h = n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			used[i][j] = false;
		}
	}
	for (int j = m; j >= 1; j--) {
		for (int i = 1; i <= last_h; i++) {
			if (a[i][j] > (mn + d)) {
				last_h = i - 1;
				break;
			}
			used[i][j] = true;
		}
	}
	if (f(d)) return true;
	return false;
}
int main() {
	mn = 1000000010;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
			mn = min(mn, a[i][j]);
		}
	}
	int l = 0, r = 1000000010, ans = -1;
	while (l <= r) {
		int mid = (l + r) / 2;
		if (ch(mid)) {
			ans = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	cout << ans << "\n";
}

Subtask #1

15.0 / 15.0

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

Subtask #2

45.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	0 ms	2396 KB	Output is correct
4	Correct	0 ms	2396 KB	Output is correct
5	Correct	1 ms	2392 KB	Output is correct
6	Correct	0 ms	2396 KB	Output is correct
7	Correct	0 ms	2396 KB	Output is correct
8	Correct	0 ms	2396 KB	Output is correct
9	Correct	0 ms	2396 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	0 ms	2396 KB	Output is correct
12	Correct	0 ms	2396 KB	Output is correct
13	Correct	0 ms	2396 KB	Output is correct
14	Correct	1 ms	2396 KB	Output is correct
15	Correct	1 ms	2392 KB	Output is correct
16	Correct	5 ms	6744 KB	Output is correct
17	Correct	8 ms	6592 KB	Output is correct
18	Correct	9 ms	6780 KB	Output is correct
19	Correct	8 ms	6748 KB	Output is correct
20	Correct	7 ms	6596 KB	Output is correct
21	Correct	12 ms	6748 KB	Output is correct
22	Correct	20 ms	6772 KB	Output is correct
23	Correct	12 ms	6748 KB	Output is correct
24	Correct	10 ms	6596 KB	Output is correct
25	Correct	12 ms	6748 KB	Output is correct
26	Correct	12 ms	6748 KB	Output is correct
27	Correct	11 ms	6748 KB	Output is correct
28	Correct	11 ms	6592 KB	Output is correct

Subtask #3

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	0 ms	2396 KB	Output is correct
4	Correct	0 ms	2396 KB	Output is correct
5	Correct	1 ms	2392 KB	Output is correct
6	Correct	0 ms	2396 KB	Output is correct
7	Correct	0 ms	2396 KB	Output is correct
8	Correct	0 ms	2396 KB	Output is correct
9	Correct	0 ms	2396 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	0 ms	2396 KB	Output is correct
12	Correct	0 ms	2396 KB	Output is correct
13	Correct	0 ms	2396 KB	Output is correct
14	Correct	1 ms	2396 KB	Output is correct
15	Correct	1 ms	2392 KB	Output is correct
16	Correct	5 ms	6744 KB	Output is correct
17	Correct	8 ms	6592 KB	Output is correct
18	Correct	9 ms	6780 KB	Output is correct
19	Correct	8 ms	6748 KB	Output is correct
20	Correct	7 ms	6596 KB	Output is correct
21	Correct	12 ms	6748 KB	Output is correct
22	Correct	20 ms	6772 KB	Output is correct
23	Correct	12 ms	6748 KB	Output is correct
24	Correct	10 ms	6596 KB	Output is correct
25	Correct	12 ms	6748 KB	Output is correct
26	Correct	12 ms	6748 KB	Output is correct
27	Correct	11 ms	6748 KB	Output is correct
28	Correct	11 ms	6592 KB	Output is correct
29	Correct	766 ms	19380 KB	Output is correct
30	Correct	700 ms	20148 KB	Output is correct
31	Correct	759 ms	20052 KB	Output is correct
32	Correct	711 ms	20048 KB	Output is correct
33	Correct	661 ms	19028 KB	Output is correct
34	Correct	703 ms	20056 KB	Output is correct
35	Correct	1012 ms	20156 KB	Output is correct
36	Correct	957 ms	20308 KB	Output is correct
37	Correct	974 ms	20048 KB	Output is correct