This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
// #define int long long
using namespace std;
int n, m, mx, mn;
vector<vector<int>> v;
int f1(int mid)
{
int x = 0;
for (int i = 0; i < n; ++i)
{
int cur = m - 1;
for (; cur >= 0; --cur)
if (v[i][cur] < mx - mid)
break;
++cur;
x = max(x, cur);
for (int j = 0; j < x; ++j)
if (v[i][j] > mn + mid)
return 0;
}
return 1;
}
int f2(int mid)
{
int x = 0;
for (int i = 0; i < n; ++i)
{
int cur = m - 1;
for (; cur >= 0; --cur)
if (v[i][cur] > mn + mid)
break;
++cur;
x = max(x, cur);
for (int j = 0; j < x; ++j)
if (v[i][j] < mx - mid)
return 0;
}
return 1;
}
int f3(int mid)
{
int x = m - 1;
for (int i = 0; i < n; ++i)
{
int cur = 0;
for (; cur < m; ++cur)
if (v[i][cur] < mx - mid)
break;
--cur;
x = min(x, cur);
for (int j = cur + 1; j < m; ++j)
if (v[i][j] > mn + mid)
return 0;
}
return 1;
}
int f4(int mid)
{
int x = m - 1;
for (int i = 0; i < n; ++i)
{
int cur = 0;
for (; cur < m; ++cur)
if (v[i][cur] > mn + mid)
break;
--cur;
x = min(x, cur);
for (int j = cur + 1; j < m; ++j)
if (v[i][j] < mx - mid)
return 0;
}
return 1;
}
void solve()
{
cin >> n >> m;
v.assign(n, vector<int>(m));
mx = 0, mn = INT_MAX;
for (auto &i : v)
for (auto &j : i)
cin >> j, mx = max(mx, j), mn = min(mn, j);
int l = 0, r = 1000000005;
while (l < r)
{
int mid = (l + r) >> 1;
if (f1(mid) || f2(mid) || f3(mid) || f4(mid))
r = mid;
else
l = mid + 1;
}
cout << l << '\n';
}
/*
4 4
1 12 6 11
11 10 2 14
10 1 9 20
4 17 19 10
8 6
23 23 10 11 16 21
15 26 19 28 19 20
25 26 28 16 15 11
11 8 19 11 15 24
14 19 15 14 24 11
10 8 11 7 6 14
23 5 19 23 17 17
18 11 21 14 20 16
*/
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |