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;
#undef wambule
#define wambule
#define sz(a) ((int)a.size())
typedef vector<int> vint;
#ifndef wambule
#include ".h"
#else
#endif
const int N = 2003, M = N;
int n, m, a[N][M], ox, on = 1e9;
void X() {
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m / 2; ++j) {
swap(a[i][j], a[i][m - 1 - j]);
}
}
}
void Y() {
for(int i = 0; i < n / 2; ++i) {
for(int j = 0; j < m; ++j) {
swap(a[i][j], a[n - 1 - i][j]);
}
}
}
bool C(int x) {
int y = m;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < y; ++j) {
if(ox - x > a[i][j]) {
y = j + 1;
break;
}
}
for(int j = y; j < m; ++j) {
if(on + x < a[i][j]) {
return 0;
}
}
}
return 1;
}
int D() {
int l = 0, r = ox - on;
while(l < r) {
int m = (l + r) / 2;
if(C(m)) {
r = m;
} else {
l = m + 1;
}
}
return l;
}
#ifdef wambule
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
cin >> a[i][j];
ox = max(ox, a[i][j]);
on = min(on, a[i][j]);
}
}
int fp = D();
Y();
fp = min(fp, D());
X();
fp = min(fp, D());
Y();
fp = min(fp, D());
cout << fp << endl;
return 0;
}
#endif
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |