#include <bits/stdc++.h>
#define int long long
#define mid(l, u) ((l+u)/2)
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
#define INF 100000000000
using namespace std;
const int N = 2005;
int n, m;
int mat[N][N];
pair<int, int> pmm[N][N];
int ourmin, ourmax;
int ind[N];
int ans = 0;
int mini = 0, maxi = INF;
set<int> el;
vector<int> dist;
void calcpmm(){
for(int i =0 ;i<n;i++){
pmm[i][m-1] = {mat[i][m-1], mat[i][m-1]};
for(int j = m-2;j>=0;j--){
pmm[i][j].first = min(mat[i][j], pmm[i][j+1].first);
pmm[i][j].second = max(mat[i][j], pmm[i][j+1].second);
}
}
}
int findinrange(int l, int u){
//cout<<endl;
//cout<<l<<" "<<u<<endl;
/*for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++) cout<<mat[i][j]<<" ";
cout<<endl;
}*/
int theirmin = INF;
int theirmax = -INF;
bool canmove = true;
for(int i =0 ;i<n;i++){
int j = ind[i];
if(canmove) {
for (; j < m && mat[i][j] >= l && mat[i][j] <= u; j++) {
ourmin = min(mat[i][j], ourmin);
ourmax = max(ourmax, mat[i][j]);
}
}
if(j==0){
if(i==0) return INF;
canmove = false;
}
if(j<m){
theirmin = min(pmm[i][j].first, theirmin);
theirmax = max(pmm[i][j].second, theirmax);
}
}
if(ourmin > ourmax || theirmin > theirmax) return INF;
//cout<<theirmax<<" "<<theirmin<<" "<<ourmax<<" "<<ourmin<<endl;
//cout<<max(theirmax - theirmin, ourmax - ourmin)<<endl;
//cout<<endl;
return max(theirmax - theirmin, ourmax - ourmin);
}
int findans(){
/*for(int i =0 ;i<n;i++){
for(int j = 0;j<m;j++) cout<<mat[i][j]<<" ";
cout<<endl;
}
cout<<endl<<endl;*/
calcpmm();
int tr = INF;
for(int i = 0;i<n;i++){
ind[i] = 0;
}
ourmin = INF;
ourmax = -INF;
int l = mini;
for(int u: dist){
if(u==maxi) break;
tr = min(tr, findinrange(l, u));
}
ourmin = INF;
ourmax = -INF;
int u = maxi;
for(int i = 0;i<n;i++) ind[i] = 0;
for(int k = dist.size()-1;k>0;k--){
tr = min(tr, findinrange(dist[k], u));
}
return tr;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>m;
int a[n][m];
for(int i =0 ;i<n;i++){
for(int j = 0;j<m;j++) {
cin >> mat[i][j];
maxi = max(maxi, mat[i][j]);
mini = min(mini, mat[i][j]);
a[i][j] = mat[i][j];
el.insert(mat[i][j]);
}
}
for(int j: el) dist.push_back(j);
ans = maxi - mini;
ans = min(ans, findans());
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++) mat[i][j] = a[i][m-j-1];
}
ans = min(ans, findans());
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++) mat[i][j] = a[n-i-1][m-j-1];
}
ans = min(ans, findans());
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++) mat[i][j] = a[n-i-1][j];
}
ans = min(ans, findans());
cout<<ans<<endl;
}
/*
4 4
1 12 6 11
11 10 2 14
10 1 9 20
4 17 19 10
8 6
23 23 10 11 16 21
15 26 19 28 19 20
25 26 28 16 15 11
11 8 19 11 15 24
14 19 15 14 24 11
10 8 11 7 6 14
23 5 19 23 17 17
18 11 21 14 20 16
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
