oj.uz

Submission #89850

# Submission time Handle Problem Language Result Execution time Memory
89850 2018-12-18T15:18:11 Z Dat160601 The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 3 ms 960 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;
	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) 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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 2 ms 880 KB Output is correct
7 Correct 2 ms 880 KB Output is correct
8 Correct 2 ms 960 KB Output is correct
9 Correct 2 ms 960 KB Output is correct
10 Correct 2 ms 960 KB Output is correct
11 Incorrect 2 ms 960 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 2 ms 880 KB Output is correct
7 Correct 2 ms 880 KB Output is correct
8 Correct 2 ms 960 KB Output is correct
9 Correct 2 ms 960 KB Output is correct
10 Correct 2 ms 960 KB Output is correct
11 Incorrect 2 ms 960 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 2 ms 880 KB Output is correct
7 Correct 2 ms 880 KB Output is correct
8 Correct 2 ms 960 KB Output is correct
9 Correct 2 ms 960 KB Output is correct
10 Correct 2 ms 960 KB Output is correct
11 Incorrect 2 ms 960 KB Output isn't correct
12 Halted 0 ms 0 KB -