#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define er erase
#define pb push_back
#define ppb pop_back()
#define ph push
#define pp pop()
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "YES" << "\n";
#define no cout << "NO" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define sqr 340
#define mod 1000000007
#define mid (l+r)/2
using namespace std;
ll h , w;
ll a[10][10];
ll b[10];
ll W(ll col , ll row , ll mn1 , ll mx1 , ll mn2 , ll mx2)
{
if(col==w-1)
{
//cout << col << " " << row << " " << mn1 << " " << mx1 << " " << mn2 << " " << mx2 << " " << max(mx1-mn1,mx2-mn2) << "\n";
return max(mx1-mn1,mx2-mn2);
}
multiset<ll> s1;
multiset<ll> s2;
for(int i = 0 ; h>i ; i++)
s2.in(a[i][col+1]);
auto it = s2.begin();
ll mn = *it;
it = s2.end();
it--;
ll mx = *it;
ll ans = W(col+1,0,mn1,mx1,min(mn2,mn),max(mx2,mx));
b[col]=0;
for(int i = 0 ; row>i ; i++)
{
s1.in(a[i][col+1]);
s2.erase(s2.find(a[i][col+1]));
it = s1.begin();
ll mnn1 = min(mn1,*it);
it = s1.end();
it--;
ll mxx1 = max(mx1,*it);
ll mnn2 = mn2;
ll mxx2 = mx2;
if(!s2.empty())
{
it = s2.begin();
mnn2=min(mnn2,*it);
it = s2.end();
it--;
mxx2=max(mxx2,*it);
}
ll ans1 = ans;
ans=min(ans,W(col+1,i+1,mnn1,mxx1,mnn2,mxx2));
if(ans!=ans1)
b[col]=i+1;
}
return ans;
}
int main()
{
d3
cin >> h >> w;
for(int i = 0 ; h>i ; i++)
for(int j = 0 ; w>j ; j++)
cin >> a[i][j];
multiset<ll> s1;
multiset<ll> s2;
for(int i = 0 ; h>i ; i++)
s2.in(a[i][0]);
ll ans = 1e10;
for(int i = 0 ; h>i ; i++)
{
s1.in(a[i][0]);
s2.erase(s2.find(a[i][0]));
auto it = s1.begin();
ll mnn1 = *it;
it = s1.end();
it--;
ll mxx1 = *it;
ll mnn2 = 1e10;
ll mxx2 = 0;
if(!s2.empty())
{
it = s2.begin();
mnn2=min(mnn2,*it);
it = s2.end();
it--;
mxx2=max(mxx2,*it);
}
//cout << i+1 << " " << mnn1 << " " << mxx1 << " " << mnn2 << " " << mxx2 << '\n';
ll ans1 = ans;
ans=min(ans,W(0,i+1,mnn1,mxx1,mnn2,mxx2));
if(ans1!=ans)
b[0]=i+1;
}
//for(int i = 0 ; w>i ; i++)
//cout << b[i] << " ";
for(int j = 0 ; w>j ; j++)
{
for(int i = 0 ; h/2>i ; i++)
{
ll x = a[i][j];
a[i][j]=a[h-i-1][j];
a[h-i][j]=x;
}
}
s1.clear();
s2.clear();
for(int i = 0 ; h>i ; i++)
s2.in(a[i][0]);
for(int i = 0 ; h>i ; i++)
{
s1.in(a[i][0]);
s2.erase(s2.find(a[i][0]));
auto it = s1.begin();
ll mnn1 = *it;
it = s1.end();
it--;
ll mxx1 = *it;
ll mnn2 = 1e10;
ll mxx2 = 0;
if(!s2.empty())
{
it = s2.begin();
mnn2=min(mnn2,*it);
it = s2.end();
it--;
mxx2=max(mxx2,*it);
}
//cout << i+1 << " " << mnn1 << " " << mxx1 << " " << mnn2 << " " << mxx2 << '\n';
ll ans1 = ans;
ans=min(ans,W(0,i+1,mnn1,mxx1,mnn2,mxx2));
if(ans1!=ans)
b[0]=i+1;
}
cans
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Runtime error |
61 ms |
456 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Runtime error |
61 ms |
456 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Runtime error |
61 ms |
456 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
