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;
#warning change mxn
const int mxn = 2005;
const int inf = 2e9;
int h, w;
int mxa = 0;
int a[mxn][mxn];
bool b[mxn][mxn];
int check() {
int mnj = w;
int mn = inf/2, mx = 0;
for(int i = 0; i < h; i++) {
for(int j = 0; j < mnj; j++) {
if(b[i][j]) mnj = j;
}
for(int j = mnj; j < w; j++) {
mn = min(mn, a[i][j]);
mx = max(mx, a[i][j]);
}
}
return mx-mn;
}
bool solve(int k) {
for(int i = 0; i < h; i++)
for(int j = 0; j < w; j++)
b[i][j] = mxa-a[i][j]>k;
bool ok = false;
// check
ok = ok || (check() <= k);
// reverse rows
for(int i = 0; i < h; i++) for(int j = 0; j < w/2; j++) swap(a[i][j], a[i][w-j-1]);
for(int i = 0; i < h; i++) for(int j = 0; j < w/2; j++) swap(b[i][j], b[i][w-j-1]);
// check
ok = ok || (check() <= k);
// reverse cols
for(int i = 0; i < h/2; i++) for(int j = 0; j < w; j++) swap(a[i][j], a[h-i-1][j]);
for(int i = 0; i < h/2; i++) for(int j = 0; j < w; j++) swap(b[i][j], b[h-i-1][j]);
// check
ok = ok || (check() <= k);
// reverse rows
for(int i = 0; i < h; i++) for(int j = 0; j < w/2; j++) swap(a[i][j], a[i][w-j-1]);
for(int i = 0; i < h; i++) for(int j = 0; j < w/2; j++) swap(b[i][j], b[i][w-j-1]);
// check
ok = ok || (check() <= k);
// reverse cols
for(int i = 0; i < h/2; i++) for(int j = 0; j < w; j++) swap(a[i][j], a[h-i-1][j]);
for(int i = 0; i < h/2; i++) for(int j = 0; j < w; j++) swap(b[i][j], b[h-i-1][j]);
return ok;
}
int main(int argc, char const *argv[]) {
cin >> h >> w;
for(int i = 0; i < h; i++) {
for(int j = 0; j < w; j++) {
cin >> a[i][j]; mxa = max(mxa, a[i][j]);
}
}
int lo = 0, hi = inf/2;
while(lo < hi) {
int m = (lo+hi)/2;
if(solve(m)) {
hi = m;
}
else {
lo = m+1;
}
}
cout << lo << "\n";
return 0;
}
Compilation message (stderr)
joioi.cpp:5:2: warning: #warning change mxn [-Wcpp]
5 | #warning change mxn
| ^~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |