#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define er erase
#define pb push_back
#define ppb pop_back()
#define ph push
#define pp pop()
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "YES" << "\n";
#define no cout << "NO" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define sqr 340
#define mod 1000000007
#define mid (l+r)/2
using namespace std;
int main()
{
//d3
ll h , w;
cin >> h >> w;
ll a[h][w];
for(int i = 0 ; h>i ; i++)
for(int j = 0 ; w>j ; j++)
cin >> a[i][j];
ll ans[h][w];
pair<pll,pll> b[h][w];
pll mnmx[w+1];
ll pmx = 0 , pmn = 1e10;
mnmx[w].F=1e10;
mnmx[w].S=0;
for(int i = w-1 ; i>=0 ; i--)
{
ll mn = 1e10 , mx = 0;
for(int j = 0 ; h>j ; j++)
{
mn=min(mn,a[j][i]);
mx=max(mx,a[j][i]);
}
mnmx[i].F=min(mn,pmn);
mnmx[i].S=max(mx,pmx);
pmn=mnmx[i].F;
pmx=mnmx[i].S;
}
multiset<ll> fc;
multiset<ll> fcc;
for(int i = 0 ; h>i ; i++)
fc.in(a[i][0]);
for(int i = 0 ; h>i ; i++)
{
fc.erase(fc.find(a[i][0]));
fcc.in(a[i][0]);
auto it = fcc.begin();
ll mn = *it;
it = fcc.end();
it--;
ll mx = *it;
ans[i][0]=mx-mn;
b[i][0].F.F=mn;
b[i][0].F.S=mx;
mn = mnmx[1].F;
mx = mnmx[1].S;
b[i][0].S.F=1e10;
b[i][0].S.S=0;
if(fc.size())
{
it = fc.begin();
b[i][0].S.F=*it;
mn=min(mn,*it);
it = fc.end();
it--;
b[i][0].S.S=*it;
mx=max(mx,*it);
}
ans[i][0] = max(ans[i][0],mx-mn);
}
//for(int i = 0 ; h>i ; i++)
//cout << b[i][0].F.F << " " << b[i][0].F.S << " " << b[i][0].S.F << " " << b[i][0].S.S << "\n";
for(int j = 1 ; w>j ; j++)
{
fc.clear();
fcc.clear();
for(int i = 0 ; h>i ; i++)
fc.in(a[i][j]);
for(int i = 0 ; h>i ; i++)
{
if(i==h-1&&j==w-1)
continue;
fc.erase(fc.find(a[i][j]));
fcc.in(a[i][j]);
auto it = fcc.begin();
ll mn1 = *it;
it=fcc.end();
it--;
ll mx1 = *it;
ll mn2 = mnmx[j+1].F;
ll mx2 = mnmx[j+1].S;
if(!fc.empty())
{
it = fc.begin();
mn2=min(mn2,*it);
it = fc.end();
it--;
mx2=max(mx2,*it);
}
ll ans1 = 1e10;
ll idx = -1;
for(int p = i ; h>p ; p++)
{
ll mnn1 = mn1;
ll mnn2 = mn2;
ll mxx1 = mx1;
ll mxx2 = mx2;
mnn1 = min(mnn1 , b[p][j-1].F.F);
mnn2 = min(mnn2 , b[p][j-1].S.F);
mxx1 = max(mxx1 , b[p][j-1].F.S);
mxx2 = max(mxx2 , b[p][j-1].S.S);
//if(j==2)
//cout << mn1 << " " << mx1 << " " << b[p][j-1].F.F << " " << b[p][j-1].F.S << "\n";
ll ans2 = max(mxx1-mnn1,mxx2-mnn2);
if(ans2<=ans1)
{
ans1=ans2;
idx=p;
}
}
//cout << i << " " << j << " " << idx << " " << j-1 << "\n";
ans[i][j]=ans1;
mn1=min(mn1,b[idx][j-1].F.F);
mx1=max(mx1,b[idx][j-1].F.S);
mx2=b[idx][j-1].S.S;
mn2=b[idx][j-1].S.F;
if(!fc.empty())
{
it = fc.begin();
mn2=min(mn2,*it);
it = fc.end();
it--;
mx2=max(mx2,*it);
}
b[i][j].F.F=mn1;
b[i][j].F.S=mx1;
b[i][j].S.F=mn2;
b[i][j].S.S=mx2;
}
}
ans[h-1][w-1]=1e10;
ll anss = 1e10;
//cout << ans[1][2] << " ";
for(int i = 0 ; h>i ; i++)
for(int j = 0 ; w>j ; j++)
anss=min(anss,ans[i][j]);
for(int j = 0 ; w>j ; j++)
{
for(int i = 0 ; h/2>i ; i++)
{
ll qq = a[i][j];
a[i][j]=a[h-i-1][j];
a[h-i-1][j]=qq;
}
}
fc.clear();
fcc.clear();
for(int i = 0 ; h>i ; i++)
fc.in(a[i][0]);
for(int i = 0 ; h>i ; i++)
{
fc.erase(fc.find(a[i][0]));
fcc.in(a[i][0]);
auto it = fcc.begin();
ll mn = *it;
it = fcc.end();
it--;
ll mx = *it;
ans[i][0]=mx-mn;
b[i][0].F.F=mn;
b[i][0].F.S=mx;
mn = mnmx[1].F;
mx = mnmx[1].S;
//cout << mn << " " << mx << "\n";
b[i][0].S.F=1e10;
b[i][0].S.S=0;
if(fc.size())
{
it = fc.begin();
b[i][0].S.F=*it;
mn=min(mn,*it);
it = fc.end();
it--;
b[i][0].S.S=*it;
mx=max(mx,*it);
}
ans[i][0] = max(ans[i][0],mx-mn);
}
//for(int i = 0 ; h>i ; i++)
//cout << b[i][0].F.F << " " << b[i][0].F.S << " " << b[i][0].S.F << " " << b[i][0].S.S << "\n";
for(int j = 1 ; w>j ; j++)
{
fc.clear();
fcc.clear();
for(int i = 0 ; h>i ; i++)
fc.in(a[i][j]);
for(int i = 0 ; h>i ; i++)
{
if(i==h-1&&j==w-1)
continue;
fc.erase(fc.find(a[i][j]));
fcc.in(a[i][j]);
auto it = fcc.begin();
ll mn1 = *it;
it=fcc.end();
it--;
ll mx1 = *it;
ll mn2 = mnmx[j+1].F;
ll mx2 = mnmx[j+1].S;
if(!fc.empty())
{
it = fc.begin();
mn2=min(mn2,*it);
it = fc.end();
it--;
mx2=max(mx2,*it);
}
ll ans1 = 1e10;
ll idx = -1;
ll mnnn1 =-1 , mxxx1 =-1 , mnnn2 =-1 , mxxx2 =-1;
for(int p = i ; h>p ; p++)
{
ll mnn1 = mn1;
ll mnn2 = mn2;
ll mxx1 = mx1;
ll mxx2 = mx2;
mnn1 = min(mnn1 , b[p][j-1].F.F);
mnn2 = min(mnn2 , b[p][j-1].S.F);
mxx1 = max(mxx1 , b[p][j-1].F.S);
mxx2 = max(mxx2 , b[p][j-1].S.S);
//if(i==4&&j==1)
//cout << mn1 << " " << mx1 << " " << b[p][j-1].F.F << " " << b[p][j-1].F.S << "\n";
ll ans2 = max(mxx1-mnn1,mxx2-mnn2);
if(ans2<ans1)
{
ans1=ans2;
idx=p;
mnnn1=mn1;
mnnn2=mn2;
mxxx1=mx1;
mxxx2=mx2;
}
else if(ans2==ans1&&mnnn1==mnn1&&mxxx1==mxx1&&mnnn2==mnn2&&mxxx2==mxx2)
{
ans1=ans2;
idx=p;
}
}
//if(i==4&&j==1)
//cout << i << " " << j << " " << idx << " " << j-1 << "\n";
ans[i][j]=ans1;
mn1=min(mn1,b[idx][j-1].F.F);
mx1=max(mx1,b[idx][j-1].F.S);
mx2=b[idx][j-1].S.S;
mn2=b[idx][j-1].S.F;
if(!fc.empty())
{
it = fc.begin();
mn2=min(mn2,*it);
it = fc.end();
it--;
mx2=max(mx2,*it);
}
b[i][j].F.F=mn1;
b[i][j].F.S=mx1;
b[i][j].S.F=mn2;
b[i][j].S.S=mx2;
}
}
ans[h-1][w-1]=1e10;
//cout << b[4][0].F.F << " " << b[4][0].F.S << " " << b[4][0].S.F << " " << b[4][0].S.S << "\n";
//cout << ans[1][2] << " ";
for(int i = 0 ; h>i ; i++)
for(int j = 0 ; w>j ; j++)
anss=min(anss,ans[i][j]);
cout << anss;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
