#include <bits/stdc++.h>
#include <bits/extc++.h>
//#define double long double
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(nullptr);
#define pb push_back
#define UNIQUE(a) sort(ALL(a));a.resize(unique(ALL(a))-a.begin());
#define ALL(X) X.begin(),X.end()
#define F(i,n) FF(i,0,(n))
#define F1(i,n) FF(i,1,(n)+1)
#define FF(i,n,m) for(int i=(int)n;i<int(m);++i)
#define rF(i,a,b) for(int i=a;i>=(int)b;--i)
#define mkp(a,b) make_pair(a,b)
#define Fi first
#define Se second
#define int ll
//#pragma GCC optimize("O3")//,unroll-loops
//#pragma GCC target("popcnt")
using namespace std;
template<typename T> bool remax(T& a, const T& b) {return b>a?a=b,1:0;}
template<typename T> bool remin(T& a, const T& b) {return b<a?a=b,1:0;}
template<typename T> void clear(T& a){
T b;
swap(a,b);
return;
}
using ll=long long;
using ull=unsigned long long;
using int128= __int128_t;
using uint128= __uint128_t;
using pii =pair<int,int> ;
const double pi=acos(-1);
const int N=2000+5;
const ll M=105;
const ll INF_64=0x3f3f3f3f3f3f3f3f;
const int INF_32=0x3f3f3f3f;
const int16_t INF_16=0x3f3f;
const int klog=20;
const int mod=1000000007;//1000000007;//998244353
const double eps=1E-3;
void gen(){
}
int a[N][N];
int mx,mn;
int n,m;
bool check(int d){
int r=0;
F(i,n){
F(j,m)
if(a[i][j]<mx-d) remax(r,j+1);
F(j,m)
if(mn+d<a[i][j]&&j<r) return false;
}
return true;
}
int bin(){
int l=0,r=mx-mn;
while(l!=r){
int m=(l+r)/2;
if(check(m)) r=m;
else l=m+1;
}
return l;
}
void Rflip(){
F(i,n/2)
F(j,m)
swap(a[i][j],a[n-1-i][j]);
}
void Cflip(){
F(i,n)
F(j,m/2)
swap(a[i][j],a[n][m-1-j]);
}
void sol(){
cin>>n>>m;
F(i,n) F(j,m){
cin>>a[i][j];
if(!(i+j))mx=mn=a[0][0];
remax(mx,a[i][j]),remin(mn,a[i][j]);
}
int an=mx-mn;
remin(an,bin());
Rflip();
remin(an,bin());
Cflip();
remin(an,bin());
Rflip();
remin(an,bin());
cout<<an<<"\n";
}
int32_t main(){
#ifdef LOCAL
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
#endif // LOCAL
IOS;
int t=1;
gen();
//cin>>t;
FF(i,1,t+1){
//cout<<"Case #"<<i<<": ";
sol();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
