#include<bits/stdc++.h>
using namespace std;
#define int long long
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 = m ; j > 0 ; -- j){
if( j == m) Min2[i][m] = Max2[i][m] = a[i][m];
else{
Min2[i][j] = min( Min2[i][j + 1] , a[i][j]);
Max2[i][j] = max( Max2[i][j + 1] , a[i][j]);
}
}
}
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);
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) );
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
