oj.uz

Submission #89853

# Submission time Handle Problem Language Result Execution time Memory
89853 2018-12-18T15:30:00 Z Dat160601 The Kingdom of JOIOI (JOI17_joioi) C++17
60 / 100
 2268 ms 263168 KB 
#include <bits/stdc++.h>
using namespace std;

int n, m, mini = 2e9, maxi = 0, a[2007][2007], sv[2007][2007];

bool Check(int x, int n, int m){
	int cur = m, mi = 2e9, mx = 0;
	bool ok = true;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= cur; j++){
			if(sv[i][j] - mini > x){
				cur = j - 1;
				break;
			}
		}
		for(int j = cur + 1; j <= m; j++){
			mi = min(mi, sv[i][j]), mx = max(mx, sv[i][j]);
		}
		if(mx - mi > x){
			ok = false;
			break;
		}
	}
	if(ok) return true;
	cur = 1, mi = 2e9, mx = 0;
	for(int i = 1; i <= n; i++){
		for(int j = m; j >= cur; j--){
			if(sv[i][j] - mini > x){
				cur = j + 1;
				break;
			}
		}
		for(int j = cur - 1; j >= 1; j--){
			mi = min(mi, sv[i][j]), mx = max(mx, sv[i][j]);
		}
		if(mx - mi > x) return false;
	}
	return true;
}

bool check(int x){
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) sv[i][j] = a[i][j];
	if(Check(x, n, m)) return true;
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) sv[i][j] = a[n - i + 1][j];
	if(Check(x, n, m)) return true;
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) sv[j][i] = a[i][j];
	if(Check(x, m, n)) return true;
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) sv[j][i] = a[i][m - j + 1];
	if(Check(x, m, n)) return true;
	return false;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
			mini = min(mini, a[i][j]);
			maxi = max(maxi, a[i][j]);
		}
	}
	int l = 0, r = maxi, mid = (l + r) / 2;
	while(l < r){
		if(check(mid)) r = mid;
		else l = mid + 1;
		mid = (l + r) / 2;
	}
	cout << mid;
}

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 628 KB Output is correct
3 Correct 2 ms 628 KB Output is correct
4 Correct 2 ms 628 KB Output is correct
5 Correct 2 ms 628 KB Output is correct
6 Correct 2 ms 628 KB Output is correct
7 Correct 2 ms 628 KB Output is correct
8 Correct 2 ms 628 KB Output is correct
9 Correct 2 ms 628 KB Output is correct
10 Correct 2 ms 660 KB Output is correct
11 Correct 2 ms 660 KB Output is correct
12 Correct 2 ms 660 KB Output is correct
13 Correct 2 ms 660 KB Output is correct
14 Correct 2 ms 744 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 628 KB Output is correct
3 Correct 2 ms 628 KB Output is correct
4 Correct 2 ms 628 KB Output is correct
5 Correct 2 ms 628 KB Output is correct
6 Correct 2 ms 628 KB Output is correct
7 Correct 2 ms 628 KB Output is correct
8 Correct 2 ms 628 KB Output is correct
9 Correct 2 ms 628 KB Output is correct
10 Correct 2 ms 660 KB Output is correct
11 Correct 2 ms 660 KB Output is correct
12 Correct 2 ms 660 KB Output is correct
13 Correct 2 ms 660 KB Output is correct
14 Correct 2 ms 744 KB Output is correct
15 Correct 3 ms 1432 KB Output is correct
16 Correct 9 ms 2720 KB Output is correct
17 Correct 14 ms 2988 KB Output is correct
18 Correct 15 ms 3276 KB Output is correct
19 Correct 13 ms 3560 KB Output is correct
20 Correct 10 ms 3708 KB Output is correct
21 Correct 16 ms 4200 KB Output is correct
22 Correct 15 ms 4604 KB Output is correct
23 Correct 15 ms 4960 KB Output is correct
24 Correct 13 ms 5252 KB Output is correct
25 Correct 15 ms 5752 KB Output is correct
26 Correct 16 ms 6140 KB Output is correct
27 Correct 16 ms 6552 KB Output is correct
28 Correct 23 ms 6916 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 628 KB Output is correct
3 Correct 2 ms 628 KB Output is correct
4 Correct 2 ms 628 KB Output is correct
5 Correct 2 ms 628 KB Output is correct
6 Correct 2 ms 628 KB Output is correct
7 Correct 2 ms 628 KB Output is correct
8 Correct 2 ms 628 KB Output is correct
9 Correct 2 ms 628 KB Output is correct
10 Correct 2 ms 660 KB Output is correct
11 Correct 2 ms 660 KB Output is correct
12 Correct 2 ms 660 KB Output is correct
13 Correct 2 ms 660 KB Output is correct
14 Correct 2 ms 744 KB Output is correct
15 Correct 3 ms 1432 KB Output is correct
16 Correct 9 ms 2720 KB Output is correct
17 Correct 14 ms 2988 KB Output is correct
18 Correct 15 ms 3276 KB Output is correct
19 Correct 13 ms 3560 KB Output is correct
20 Correct 10 ms 3708 KB Output is correct
21 Correct 16 ms 4200 KB Output is correct
22 Correct 15 ms 4604 KB Output is correct
23 Correct 15 ms 4960 KB Output is correct
24 Correct 13 ms 5252 KB Output is correct
25 Correct 15 ms 5752 KB Output is correct
26 Correct 16 ms 6140 KB Output is correct
27 Correct 16 ms 6552 KB Output is correct
28 Correct 23 ms 6916 KB Output is correct
29 Correct 1150 ms 57952 KB Output is correct
30 Correct 1455 ms 80152 KB Output is correct
31 Correct 1362 ms 103400 KB Output is correct
32 Correct 1383 ms 126416 KB Output is correct
33 Correct 1349 ms 144356 KB Output is correct
34 Correct 1403 ms 169744 KB Output is correct
35 Correct 2268 ms 207896 KB Output is correct
36 Correct 1591 ms 238688 KB Output is correct
37 Runtime error 2149 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.