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>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
using ll = long long;
const ll inf = 1e18;
const int maxn = 2020;
int n,m;
ll g[maxn][maxn];
ll tmp[maxn][maxn];
ll mn = inf;
ll mx = -inf;
bool test(ll diff) {
{
int sep = 0;
bool ok = true;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if (g[i][j]<mx-diff) {
sep = max(sep,j+1);
}
}
for (int j=0; j<m; j++) {
if (g[i][j]>mn+diff) {
if (j<sep) ok = false;
}
}
}
if (ok) return true;
}
{
int sep = 0;
bool ok = true;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if (g[i][j]>mn+diff) {
sep = max(sep,j+1);
}
}
for (int j=0; j<m; j++) {
if (g[i][j]<mx-diff) {
if (j<sep) ok = false;
}
}
}
if (ok) return true;
}
return false;
}
ll solve() {
ll diff = mx-mn;
ll hi = diff;
ll lo = -1;
while (hi-lo>1) {
ll mid = (lo+hi)/2;
if (test(mid)) {
hi = mid;
} else {
lo = mid;
}
}
return hi;
}
void flipY() {
for (int i=0; i<n; i++) {
for (int j=0; j<m/2; j++) {
swap(g[i][j],g[i][m-j-1]);
}
}
}
void transpose() {
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
tmp[j][i]=g[i][j];
}
}
swap(n,m);
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
g[i][j]=tmp[i][j];
}
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>m;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
cin>>g[i][j];
}
}
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
mn = min(mn, g[i][j]);
mx = max(mx, g[i][j]);
}
}
ll res = inf;
res = min(res, solve());
flipY();
res = min(res, solve());
flipY(); transpose();
res = min(res, solve());
flipY();
res = min(res, solve());
cout<<res<<endl;
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... |