#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <numeric>
#include <cassert>
#define endl '\n'
#define sp ' '
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int maxn = 2005;
ll arr[maxn][maxn];
bool boya[maxn][maxn];
const ll inf = 1e9;
int h,w;
ll ans = inf;
ll calc(){
ll joimin=inf,joimax = 0,ioimin=inf,ioimax=0;
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
if(boya[i][j]){
ioimax = max(ioimax,arr[i][j]);
ioimin = min(ioimin,arr[i][j]);
}
else{
joimax = max(joimax,arr[i][j]);
joimin = min(joimin,arr[i][j]);
}
}
}
if(ioimin == inf || joimin == inf) return inf;
return max(ioimax - ioimin, joimax - joimin);
}
void f(int derin, int kac){
if(derin < 0) return;
for(int i=0;i<w;i++) boya[derin][i] = false;
for(int i=0;i<kac;i++){
boya[derin][i] = true;
ans = min(ans, calc());
f(derin-1,i+1);
}
for(int i=0;i<w;i++) boya[derin][i] = false;
}
ll temprot[maxn][maxn];
void rot(){
for(int i=0;i<w;i++){
for(int j=0;j<h;j++){
temprot[i][j] = arr[h-j-1][i];
}
}
for(int i=0;i<w;i++){
for(int j=0;j<h;j++){
arr[i][j] = temprot[i][j];
}
}
swap(h,w);
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cerr.tie(nullptr);
cin>>h>>w;
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
cin>>arr[i][j];
}
}
for(int i=0;i<4;i++){
f(h-1,w);
/*
for(int k=0;k<h;k++){
for(int l=0;l<w;l++)
cout<<arr[k][l]<<sp;
cout<<endl;
}
cout<<endl;
*/
rot();
}
cout << ans << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
364 KB |
Output is correct |
2 |
Correct |
2 ms |
492 KB |
Output is correct |
3 |
Correct |
141 ms |
620 KB |
Output is correct |
4 |
Correct |
66 ms |
492 KB |
Output is correct |
5 |
Correct |
145 ms |
492 KB |
Output is correct |
6 |
Correct |
31 ms |
492 KB |
Output is correct |
7 |
Correct |
139 ms |
492 KB |
Output is correct |
8 |
Correct |
139 ms |
492 KB |
Output is correct |
9 |
Correct |
139 ms |
492 KB |
Output is correct |
10 |
Correct |
139 ms |
492 KB |
Output is correct |
11 |
Correct |
142 ms |
496 KB |
Output is correct |
12 |
Correct |
139 ms |
620 KB |
Output is correct |
13 |
Correct |
140 ms |
492 KB |
Output is correct |
14 |
Correct |
141 ms |
492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
364 KB |
Output is correct |
2 |
Correct |
2 ms |
492 KB |
Output is correct |
3 |
Correct |
141 ms |
620 KB |
Output is correct |
4 |
Correct |
66 ms |
492 KB |
Output is correct |
5 |
Correct |
145 ms |
492 KB |
Output is correct |
6 |
Correct |
31 ms |
492 KB |
Output is correct |
7 |
Correct |
139 ms |
492 KB |
Output is correct |
8 |
Correct |
139 ms |
492 KB |
Output is correct |
9 |
Correct |
139 ms |
492 KB |
Output is correct |
10 |
Correct |
139 ms |
492 KB |
Output is correct |
11 |
Correct |
142 ms |
496 KB |
Output is correct |
12 |
Correct |
139 ms |
620 KB |
Output is correct |
13 |
Correct |
140 ms |
492 KB |
Output is correct |
14 |
Correct |
141 ms |
492 KB |
Output is correct |
15 |
Execution timed out |
4075 ms |
492 KB |
Time limit exceeded |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
364 KB |
Output is correct |
2 |
Correct |
2 ms |
492 KB |
Output is correct |
3 |
Correct |
141 ms |
620 KB |
Output is correct |
4 |
Correct |
66 ms |
492 KB |
Output is correct |
5 |
Correct |
145 ms |
492 KB |
Output is correct |
6 |
Correct |
31 ms |
492 KB |
Output is correct |
7 |
Correct |
139 ms |
492 KB |
Output is correct |
8 |
Correct |
139 ms |
492 KB |
Output is correct |
9 |
Correct |
139 ms |
492 KB |
Output is correct |
10 |
Correct |
139 ms |
492 KB |
Output is correct |
11 |
Correct |
142 ms |
496 KB |
Output is correct |
12 |
Correct |
139 ms |
620 KB |
Output is correct |
13 |
Correct |
140 ms |
492 KB |
Output is correct |
14 |
Correct |
141 ms |
492 KB |
Output is correct |
15 |
Execution timed out |
4075 ms |
492 KB |
Time limit exceeded |
16 |
Halted |
0 ms |
0 KB |
- |