#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=2050;
int n,m,a[N][N];
vector<pair<int,int>> ord;
int ans=-1,mx=1,mn=1e9,now;
bool was[N][N];
void Solve(vector<pair<int,int>> Move)
{
now=mx;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) was[i][j]=0;
for(auto p:ord)
{
int x,y;
tie(x,y)=p;
int tmp=max(a[x][y]-mn,mx-now);
if(ans==-1 || ans>tmp) ans=tmp;
if(!was[x][y])
{
queue<pair<int,int>> q;
auto push=[&](int i, int j)
{
q.push({i,j});
was[i][j]=1;
now=min(now,a[i][j]);
};
push(x,y);
while(q.size())
{
tie(x,y)=q.front();
q.pop();
for(auto mv:Move)
{
int nx,ny;
nx=x+mv.first;
ny=y+mv.second;
if(nx>=1 && nx<=n && ny>=1 && ny<=m && !was[nx][ny]) push(nx,ny);
}
}
}
}
}
int main()
{
scanf("%i %i",&n,&m);
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%i",&a[i][j]),ord.pb({i,j}),mx=max(mx,a[i][j]),mn=min(mn,a[i][j]);
sort(ord.begin(),ord.end(),[&](pair<int,int> x, pair<int,int> y){ return a[x.first][x.second]>a[y.first][y.second];});
Solve({{-1,0},{0,-1}});
Solve({{-1,0},{0,1}});
Solve({{1,0},{0,-1}});
Solve({{1,0},{0,1}});
printf("%i\n",ans);
return 0;
}
Compilation message
joioi.cpp: In function 'int main()':
joioi.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i",&n,&m);
~~~~~^~~~~~~~~~~~~~~
joioi.cpp:47:99: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%i",&a[i][j]),ord.pb({i,j}),mx=max(mx,a[i][j]),mn=min(mn,a[i][j]);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
504 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
504 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
3 ms |
508 KB |
Output is correct |
| 16 |
Correct |
13 ms |
2364 KB |
Output is correct |
| 17 |
Correct |
19 ms |
2544 KB |
Output is correct |
| 18 |
Correct |
18 ms |
2540 KB |
Output is correct |
| 19 |
Correct |
18 ms |
2552 KB |
Output is correct |
| 20 |
Correct |
19 ms |
2416 KB |
Output is correct |
| 21 |
Correct |
20 ms |
2672 KB |
Output is correct |
| 22 |
Correct |
20 ms |
2672 KB |
Output is correct |
| 23 |
Correct |
20 ms |
2672 KB |
Output is correct |
| 24 |
Correct |
18 ms |
2544 KB |
Output is correct |
| 25 |
Correct |
20 ms |
2784 KB |
Output is correct |
| 26 |
Correct |
20 ms |
2672 KB |
Output is correct |
| 27 |
Correct |
20 ms |
2676 KB |
Output is correct |
| 28 |
Correct |
21 ms |
2672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
504 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
3 ms |
508 KB |
Output is correct |
| 16 |
Correct |
13 ms |
2364 KB |
Output is correct |
| 17 |
Correct |
19 ms |
2544 KB |
Output is correct |
| 18 |
Correct |
18 ms |
2540 KB |
Output is correct |
| 19 |
Correct |
18 ms |
2552 KB |
Output is correct |
| 20 |
Correct |
19 ms |
2416 KB |
Output is correct |
| 21 |
Correct |
20 ms |
2672 KB |
Output is correct |
| 22 |
Correct |
20 ms |
2672 KB |
Output is correct |
| 23 |
Correct |
20 ms |
2672 KB |
Output is correct |
| 24 |
Correct |
18 ms |
2544 KB |
Output is correct |
| 25 |
Correct |
20 ms |
2784 KB |
Output is correct |
| 26 |
Correct |
20 ms |
2672 KB |
Output is correct |
| 27 |
Correct |
20 ms |
2676 KB |
Output is correct |
| 28 |
Correct |
21 ms |
2672 KB |
Output is correct |
| 29 |
Correct |
2163 ms |
49460 KB |
Output is correct |
| 30 |
Correct |
2081 ms |
71268 KB |
Output is correct |
| 31 |
Correct |
2368 ms |
75032 KB |
Output is correct |
| 32 |
Correct |
2307 ms |
74920 KB |
Output is correct |
| 33 |
Correct |
1752 ms |
65560 KB |
Output is correct |
| 34 |
Correct |
2244 ms |
75164 KB |
Output is correct |
| 35 |
Correct |
2738 ms |
90524 KB |
Output is correct |
| 36 |
Correct |
2095 ms |
81420 KB |
Output is correct |
| 37 |
Correct |
2572 ms |
90632 KB |
Output is correct |
