// In The Name Of The Queen
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimzie("O3")
#pragma GCC target("AVX")
using namespace std;
const int N = 2019, INF = 1e9 + 1;
int n, m, A[N][N], P[N], S[N], B[N];
pair < int , int > At[2];
int Val[2];
inline int Solve(int md)
{
for (int w = 0; w <= 1; w ++)
{
P[0] = 0; S[m + 1] = INF;
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= m; j ++)
P[j] = max(P[j - 1], A[i][j]);
for (int j = m; j; j --)
S[j] = min(S[j + 1], A[i][j]);
B[i] = m + 1;
int l = B[i - 1], r = m;
if (At[0].first == i)
l = max(l, At[0].second);
if (At[1].first == i)
r = min(r, At[1].second - 1);
for (int j = l; j <= r; j ++)
{
if (P[j] - Val[0] > md)
break;
if (Val[1] - S[j + 1] > md)
continue;
B[i] = j;
break;
}
}
if (B[n] <= m)
return 1;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
A[i][j] = INF - A[i][j];
Val[0] = INF - Val[0];
Val[1] = INF - Val[1];
swap(Val[0], Val[1]);
swap(At[0], At[1]);
}
return 0;
}
inline int Run()
{
Val[0] = INT_MAX;
Val[1] = INT_MIN;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
{
if (Val[0] > A[i][j])
Val[0] = A[i][j], At[0] = {i, j};
if (Val[1] < A[i][j])
Val[1] = A[i][j], At[1] = {i, j};
}
int le = -1, ri = Val[1] - Val[0], md;
while (ri - le > 1)
{
md = (le + ri) >> 1;
if (Solve(md))
ri = md;
else
le = md;
}
return (ri);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
scanf("%d", &A[i][j]);
int Mn = Run();
for (int i = 1; i < n - i + 1; i ++)
for (int j = 1; j <= m; j ++)
swap(A[i][j], A[n - i + 1][j]);
Mn = min(Mn, Run());
return !printf("%d\n", Mn);
}
Compilation message
joioi.cpp:4:0: warning: ignoring #pragma GCC optimzie [-Wunknown-pragmas]
#pragma GCC optimzie("O3")
joioi.cpp:5:25: error: attribute(target("AVX")) is unknown
#pragma GCC target("AVX")
^
joioi.cpp: In function 'int main()':
joioi.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
joioi.cpp:78:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &A[i][j]);
~~~~~^~~~~~~~~~~~~~~~
