#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];
int mark[maxn][maxn];
bool test(ll diff) {
ll mn = inf;
ll mx = -inf;
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]);
}
}
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
mark[i][j] = -1;
}
}
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if (mark[i][j]==-1) {
if (g[i][j]<mx-diff) {
mark[i][j]=0;
} else if (mn+diff<g[i][j]) {
mark[i][j]=1;
}
}
}
}
int right0 = m-1;
for (int i=0; i<n; i++) {
int r0 = 0;
int l1 = m;
for (int j=0; j<m; j++) {
if (mark[i][j]==0) {
r0=j;
} else if (mark[i][j]==1) {
l1=min(l1,j);
}
}
if (r0>l1) return false;
if (r0>right0) return false;
right0 = min(right0, l1-1);
//watch(right0);
}
return true;
}
ll solve() {
ll mn = inf;
ll mx = -inf;
vector<ll> a;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
a.push_back(g[i][j]);
mn = min(mn, g[i][j]);
mx = max(mx, g[i][j]);
}
}
sort(a.begin(),a.end());
ll res = inf;
for (ll x: a) {
for (ll y: a) {
if (x<y) {
if (test(y-x)) {
res = min(res, y-x);
}
}
}
}
return res;
}
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];
}
}
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 |
1 |
Correct |
2 ms |
492 KB |
Output is correct |
2 |
Correct |
1 ms |
492 KB |
Output is correct |
3 |
Correct |
9 ms |
492 KB |
Output is correct |
4 |
Incorrect |
8 ms |
492 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
492 KB |
Output is correct |
2 |
Correct |
1 ms |
492 KB |
Output is correct |
3 |
Correct |
9 ms |
492 KB |
Output is correct |
4 |
Incorrect |
8 ms |
492 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
492 KB |
Output is correct |
2 |
Correct |
1 ms |
492 KB |
Output is correct |
3 |
Correct |
9 ms |
492 KB |
Output is correct |
4 |
Incorrect |
8 ms |
492 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |