oj.uz

Submission #1051688

# Submission time Handle Problem Language Result Execution time Memory
1051688 2024-08-10T09:03:59 Z alex_2008 The Kingdom of JOIOI (JOI17_joioi) C++14
15 / 100
 5 ms 6744 KB 
#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 + 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 = 1; j <= m; j++) {
		for (int i = n; i >= n - last_h + 1; i--) {
			if (a[i][j] > (mn + d)) {
				last_h = n - 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 = 1; j <= m; j++) {
		for (int i = 1; i <= last_h; i++) {
			if (a[i][j] > (mn + d)) {
				last_h = 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 = m; j >= 1; j--) {
		for (int i = 1; i <= last_h; i++) {
			if (a[i][j] > (mn + d)) {
				last_h = i;
				break;
			}
			used[i][j] = true;
		}
	}
	if (f(d)) return true;
	return false;
}
int main() {
  	ios_base::sync_with_stdio(false); cin.tie(0);
	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 0 ms 2396 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 0 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 0 ms 2396 KB Output is correct

Subtask #2
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 0 ms 2396 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 0 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 0 ms 2396 KB Output is correct
15 Correct 1 ms 2648 KB Output is correct
16 Correct 3 ms 6744 KB Output is correct
17 Incorrect 5 ms 6616 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
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 0 ms 2396 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 0 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 0 ms 2396 KB Output is correct
15 Correct 1 ms 2648 KB Output is correct
16 Correct 3 ms 6744 KB Output is correct
17 Incorrect 5 ms 6616 KB Output isn't correct
18 Halted 0 ms 0 KB -