oj.uz

Submission #51534

# Submission time Handle Problem Language Result Execution time Memory
51534 2018-06-18T08:03:12 Z huynhsmd The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 2 ms 612 KB 
#include<bits/stdc++.h>

using namespace std;

const int N=2005;

int n , m , ans1 , ans2;
int a[N][N] , b[N][N] , Min1[N][N] , Max1[N][N] , Min2[N][N] , Max2[N][N];

bool check1(int mid , int n , int m){
	for(int i = 1 ; i <= n ; ++ i){
		int ok = 0;
		for(int j = 0 ; j < m ;++ j)
			if(Max1[i][j] - Min1[i][j] <= mid && Max2[i][j + 1] - Min2[i][j + 1] <= mid){
				ok = 1;
				break;
			}
		if(!ok)
			return false;
	}
	return true;
}
int solve(int a[N][N] , int n , int m){
	for(int i = 1 ; i <= n ; ++ i){
		for(int j = 1 ; j <= m ;++ j){
			if( j == 1) Min1[i][1] = Max1[i][1] = a[i][1];
			else{
				Min1[i][j] = min( Min1[i][j - 1] , a[i][j]);
				Max1[i][j] = max( Max1[i][j - 1] , a[i][j]);
			}
		}
		for(int j = n ; j > 0 ; -- j){
			if( j == m) Min2[i][n] = Max2[i][n] = a[i][n];
			else{
				Min2[i][j] = min( Min2[i][j + 1] , a[i][j]);
				Max2[i][j] = max( Max2[i][j + 1] , a[i][j]);
			}
		}
	}
	/*for(int i = 1 ; i <= n ; ++ i){
		for(int j = 1 ; j <= m ;++ j)
			cout << Min1[i][j] << ' ' << Max1[i][j] << " ? ";
		cout <<endl;
	}
	
	for(int i = 1 ; i <= n ; ++ i){
		for(int j = 1 ; j <= m ;++ j)
			cout << Min2[i][j] << ' ' << Max2[i][j] << " ? ";
		cout <<endl;
	}
	cout <<endl;
	*/
	int l = 0, r = 1e9 , res = r;
	while(l <= r){
		int mid = (l + r) / 2;
		bool kt = check1(mid , n , m);
		if(kt){
			res = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	return res;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("1.inp","r",stdin);
	cin >> n >> m;
	for(int i = 1 ; i <= n ; ++ i)
		for(int j = 1 ; j <= m ;++ j)
			cin >> a[i][j];
	for(int j = 1 ; j <= m ; ++ j)
		for(int i = 1 ; i <= n ; ++ i)
			b[j][i] = a[i][j];	
	cout << max(solve(a , n , m) , solve(b , m , n) );
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Incorrect 2 ms 612 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Incorrect 2 ms 612 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Incorrect 2 ms 612 KB Output isn't correct
3 Halted 0 ms 0 KB -