#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int nmax=2005;
int a[nmax][nmax];
int mn,mx,ans,n,m,i,j;
bool check(int val)
{
int st=0,dr=m,l,r;
bool cresc=1,desc=1;
for(i=1;i<=n&&(cresc||desc);i++)
{
r=1;l=m;
while(a[i][r]-mn<=val&&r<=m)
r++;
r--;
while(mx-a[i][l]<=val&&l>0)
l--;
st=max(st,l);dr=min(r,dr);
if(st>r)
cresc=0;
if(dr<l)
desc=0;
}
return (cresc||desc);
}
int solve()
{
int ret=(1<<30)-1;
for(int p=29;p>=0;p--)
if(check(ret-(1<<p)))
ret-=(1<<p);
return ret;
}
int main()
{
// freopen("data.in","r",stdin);
ios_base::sync_with_stdio(false);
cin>>n>>m;mn=(1<<30);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
cin>>a[i][j];
mn=min(a[i][j],mn);
mx=max(a[i][j],mx);
}
ans=mx-mn;
ans=min(solve(),ans);
for(i=1;i<=n;i++)
for(j=1;j<=m/2;j++)
swap(a[i][j],a[i][m-j+1]);
ans=min(solve(),ans);
cout<<ans;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
420 KB |
Output is correct |
| 2 |
Correct |
2 ms |
420 KB |
Output is correct |
| 3 |
Correct |
2 ms |
456 KB |
Output is correct |
| 4 |
Correct |
2 ms |
632 KB |
Output is correct |
| 5 |
Correct |
2 ms |
712 KB |
Output is correct |
| 6 |
Correct |
2 ms |
712 KB |
Output is correct |
| 7 |
Correct |
2 ms |
712 KB |
Output is correct |
| 8 |
Correct |
2 ms |
744 KB |
Output is correct |
| 9 |
Correct |
2 ms |
744 KB |
Output is correct |
| 10 |
Correct |
2 ms |
744 KB |
Output is correct |
| 11 |
Correct |
2 ms |
744 KB |
Output is correct |
| 12 |
Correct |
2 ms |
744 KB |
Output is correct |
| 13 |
Correct |
2 ms |
744 KB |
Output is correct |
| 14 |
Correct |
2 ms |
744 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
420 KB |
Output is correct |
| 2 |
Correct |
2 ms |
420 KB |
Output is correct |
| 3 |
Correct |
2 ms |
456 KB |
Output is correct |
| 4 |
Correct |
2 ms |
632 KB |
Output is correct |
| 5 |
Correct |
2 ms |
712 KB |
Output is correct |
| 6 |
Correct |
2 ms |
712 KB |
Output is correct |
| 7 |
Correct |
2 ms |
712 KB |
Output is correct |
| 8 |
Correct |
2 ms |
744 KB |
Output is correct |
| 9 |
Correct |
2 ms |
744 KB |
Output is correct |
| 10 |
Correct |
2 ms |
744 KB |
Output is correct |
| 11 |
Correct |
2 ms |
744 KB |
Output is correct |
| 12 |
Correct |
2 ms |
744 KB |
Output is correct |
| 13 |
Correct |
2 ms |
744 KB |
Output is correct |
| 14 |
Correct |
2 ms |
744 KB |
Output is correct |
| 15 |
Correct |
3 ms |
744 KB |
Output is correct |
| 16 |
Correct |
12 ms |
1880 KB |
Output is correct |
| 17 |
Correct |
12 ms |
1972 KB |
Output is correct |
| 18 |
Correct |
12 ms |
2260 KB |
Output is correct |
| 19 |
Correct |
13 ms |
2528 KB |
Output is correct |
| 20 |
Correct |
11 ms |
2676 KB |
Output is correct |
| 21 |
Correct |
12 ms |
3168 KB |
Output is correct |
| 22 |
Correct |
12 ms |
3572 KB |
Output is correct |
| 23 |
Correct |
12 ms |
3956 KB |
Output is correct |
| 24 |
Correct |
10 ms |
4232 KB |
Output is correct |
| 25 |
Correct |
12 ms |
4708 KB |
Output is correct |
| 26 |
Correct |
13 ms |
5108 KB |
Output is correct |
| 27 |
Correct |
13 ms |
5484 KB |
Output is correct |
| 28 |
Correct |
18 ms |
5872 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
420 KB |
Output is correct |
| 2 |
Correct |
2 ms |
420 KB |
Output is correct |
| 3 |
Correct |
2 ms |
456 KB |
Output is correct |
| 4 |
Correct |
2 ms |
632 KB |
Output is correct |
| 5 |
Correct |
2 ms |
712 KB |
Output is correct |
| 6 |
Correct |
2 ms |
712 KB |
Output is correct |
| 7 |
Correct |
2 ms |
712 KB |
Output is correct |
| 8 |
Correct |
2 ms |
744 KB |
Output is correct |
| 9 |
Correct |
2 ms |
744 KB |
Output is correct |
| 10 |
Correct |
2 ms |
744 KB |
Output is correct |
| 11 |
Correct |
2 ms |
744 KB |
Output is correct |
| 12 |
Correct |
2 ms |
744 KB |
Output is correct |
| 13 |
Correct |
2 ms |
744 KB |
Output is correct |
| 14 |
Correct |
2 ms |
744 KB |
Output is correct |
| 15 |
Correct |
3 ms |
744 KB |
Output is correct |
| 16 |
Correct |
12 ms |
1880 KB |
Output is correct |
| 17 |
Correct |
12 ms |
1972 KB |
Output is correct |
| 18 |
Correct |
12 ms |
2260 KB |
Output is correct |
| 19 |
Correct |
13 ms |
2528 KB |
Output is correct |
| 20 |
Correct |
11 ms |
2676 KB |
Output is correct |
| 21 |
Correct |
12 ms |
3168 KB |
Output is correct |
| 22 |
Correct |
12 ms |
3572 KB |
Output is correct |
| 23 |
Correct |
12 ms |
3956 KB |
Output is correct |
| 24 |
Correct |
10 ms |
4232 KB |
Output is correct |
| 25 |
Correct |
12 ms |
4708 KB |
Output is correct |
| 26 |
Correct |
13 ms |
5108 KB |
Output is correct |
| 27 |
Correct |
13 ms |
5484 KB |
Output is correct |
| 28 |
Correct |
18 ms |
5872 KB |
Output is correct |
| 29 |
Correct |
883 ms |
41976 KB |
Output is correct |
| 30 |
Correct |
916 ms |
64272 KB |
Output is correct |
| 31 |
Correct |
878 ms |
87488 KB |
Output is correct |
| 32 |
Correct |
907 ms |
110560 KB |
Output is correct |
| 33 |
Correct |
789 ms |
128624 KB |
Output is correct |
| 34 |
Correct |
895 ms |
153800 KB |
Output is correct |
| 35 |
Correct |
937 ms |
192540 KB |
Output is correct |
| 36 |
Correct |
780 ms |
226312 KB |
Output is correct |
| 37 |
Runtime error |
906 ms |
263168 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
