#include <bits/stdc++.h>
#define ll long long
#define pi pair<ll,ll>
#define mid (l+r)/2
#define pb push
using namespace std;
const ll inf = 2e3+9,MX = 1e9+9;
ll n,m,ts,a[inf][inf],mn = MX,mx,vis[inf][inf];
pi MaxVals;
queue<ll> q;
bool check(ll k,bool is){
q.pb(MaxVals.second);
ts++;
while(!q.empty()){
ll j = q.front();
q.pop();
if(j<1 || j>m || vis[0][j] == ts)
continue;
vis[0][j] = ts;
ll i;
if(is){
for(i=1;i<=n && a[i][j] >= mx-k;i++)
vis[i][j] = ts;
i--;
if(i>0)
q.pb(j-1),q.pb(j+1);
}
else {
for(i=n;i>=1 && a[i][j] >= mx-k;i--)
vis[i][j] = ts;
i++;
if(i<=n)
q.pb(j-1),q.pb(j+1);
}
}
for(ll i=1;i<=n;i++)
for(ll j=1;j<=m;j++)
if(vis[i][j] != ts && a[i][j] > mn + k)
return 0;
return 1;
}
signed main(){
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=n;i++){
for(ll j=1;j<=m;j++){
scanf("%lld",&a[i][j]);
if(a[i][j] > mx)
MaxVals = (pi(i,j)),mx = a[i][j];
mn = min(mn,a[i][j]);
}
}
ll l = -1, r = MX;
while(r-l>1){
if(check(mid,0) || check(mid,1))
r = mid;
else
l = mid;
}
printf("%lld\n",r);
}
Compilation message
monster.cpp: In function 'int main()':
monster.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | scanf("%lld%lld",&n,&m);
| ~~~~~^~~~~~~~~~~~~~~~~~
monster.cpp:50:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
50 | scanf("%lld",&a[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccTbBIiA.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cctV9Pjz.o:monster.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccTbBIiA.o: in function `main':
stub.cpp:(.text.startup+0xb3): undefined reference to `Solve(int)'
collect2: error: ld returned 1 exit status
