#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 check1(ll k){
ts++;
ll l = n,r;
for(ll j=1;j<=m;j++){
ll LastReq = 0;
for(ll i=1;i<=n;i++)
if(a[i][j] > mn+k)
LastReq = i;
for(ll i=1;i<=LastReq;i++){
if(a[i][j] < mx-k)
return 0;
vis[i][j] = ts;
}
if(LastReq)
l = min(l,j),r = j;
}
for(ll j=l;j<=r;j++){
if(a[1][j] < mx-k)
return 0;
vis[1][j] = ts;
}
ts++;
l = n;
for(ll j=1;j<=m;j++){
ll LastReq = n+1;
for(ll i=n;i>=1;i--)
if(a[i][j] < mx-k)
LastReq = i;
for(ll i=n;i>=LastReq;i--){
if(a[i][j] > mn+k || vis[i][j] == ts-1)
return 0;
vis[i][j] = ts;
}
if(LastReq < n+1)
l = min(l,j),r = j;
}
for(ll j=l;j<=r;j++){
if(a[n][j] > mn+k || vis[n][j] == ts-1)
return 0;
vis[n][j] = ts;
}
return 1;
}
bool check2(ll k){
ts++;
ll l = n,r;
for(ll j=1;j<=m;j++){
ll LastReq = n+1;
for(ll i=n;i>=1;i--)
if(a[i][j] > mn+k)
LastReq = i;
for(ll i=n;i>=LastReq;i--){
if(a[i][j] < mx-k)
return 0;
vis[i][j] = ts;
}
if(LastReq < n+1)
l = min(l,j),r = j;
}
for(ll j=l;j<=r;j++){
if(a[n][j] < mx-k)
return 0;
vis[n][j] = ts;
}
ts++;
l = n;
for(ll j=1;j<=m;j++){
ll LastReq = 0;
for(ll i=1;i<=n;i++)
if(a[i][j] < mx-k)
LastReq = i;
for(ll i=1;i<=LastReq;i++){
if(a[i][j] > mn+k || vis[i][j] == ts-1)
return 0;
vis[i][j] = ts;
}
if(LastReq)
l = min(l,j),r = j;
}
for(ll j=l;j<=r;j++){
if(a[1][j] > mn+k || vis[1][j] == ts-1)
return 0;
vis[1][j] = ts;
}
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+2;
while(r-l>1){
if(check1(mid) || check2(mid))
r = mid;
else
l = mid;
}
printf("%lld\n",r);
}
Compilation message
joioi.cpp: In function 'int main()':
joioi.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
100 | scanf("%lld%lld",&n,&m);
| ~~~~~^~~~~~~~~~~~~~~~~~
joioi.cpp:103:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
103 | scanf("%lld",&a[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~~
joioi.cpp: In function 'bool check1(long long int)':
joioi.cpp:28:17: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
28 | for(ll j=l;j<=r;j++){
| ~^~~
joioi.cpp: In function 'bool check2(long long int)':
joioi.cpp:72:17: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
72 | for(ll j=l;j<=r;j++){
| ~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
31948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
31948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
31948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
