| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1199547 | hyl_backup | The Kingdom of JOIOI (JOI17_joioi) | C++20 | 0 ms | 0 KiB |
//The Kingdom of JOIOI
#include <iostream>
#include <set>
#include <math.h>
#include <vector>
#define MIN(a, b) ((a<b)? a :b )
#define MAX(a, b) ((a>b)? a :b )
long long h, w, min, max, col, a, b, min_a, min_b, max_a, max_b;
long long limit, ans;
long long mat[2007][2007];
std::set<std::pair<long long, long long>> set;
std::multiset<long long> og;
std::multiset<long long> ms_a;
std::multiset<long long> ms_b;
std::multiset<long long> ms_b1;
struct node{
long long min;
long long max;
};
node tree[207][807];
void b_tree(int pos=1, int l=0, int r=h-1){
if(l==r){
tree[pos][col].max=mat[l][col];
tree[pos][col].min=mat[l][col];
return;
}
int m = (l+r)/2;
b_tree(pos*2, l, m);
b_tree(pos*2+1, m+1, r);
tree[pos][col].max =MAX(tree[pos*2][col].max, tree[pos*2+1][col].max);
tree[pos][col].min =MIN(tree[pos*2][col].min, tree[pos*2+1][col].min);
}
long long min_tree(int pos = 1, int l=0, int r=h-1){
if(l>=a && r<=b){
return tree[pos][col].min;
}
int m = (l+r)/2;
long long cat = LLONG_MAX;
if(m<b){
cat = MIN(cat, min_tree(pos*2+1, m+1, r));
}
if(m>=a){
cat = MIN(cat, min_tree(pos*2, l, m));
}
return cat;
}
long long max_tree(int pos = 1, int l=0, int r=h-1){
if(l>=a && r<=b){
return tree[pos][col].max;
}
int m = (l+r)/2;
long long cat = LLONG_MIN;
if(m<b){
cat = MAX(cat, max_tree(pos*2+1, m+1, r));
}
if(m>=a){
cat = MAX(cat, max_tree(pos*2, l, m));
}
return cat;
}
std::set<std::vector<int>> dp;
std::set<std::vector<int>> dp2;
int main(){
std::cin.tie(0);
std::ios_base::sync_with_stdio(0);
std::cin >> h >> w;
for(int i = 0; i<h; ++i){
for(int j = 0; j<w; ++j){
std::cin >> mat[i][j];
og.insert(mat[i][j]);
}
}
min = LLONG_MAX;
for(int j = 0; j<w; ++j){
col=j;
b_tree();
}
a = 1;
b = 2;
//std::cout << min_tree() << ' ' << max_tree()<<'\n';
ans = LLONG_MAX;
//ms_b=og;
dp.insert({h-1, 2000123000, 0, 2000123000, 0});
for(int j = 0; j<=w; ++j){
for(std::vector<int> x : dp){
//limit, min, max, min, max
/*
std::cout << j<<"pos ";
for(int c : x){
std::cout << c <<' ';
}
std::cout <<'\n';
*/
limit=x[0];
if(j==w){
ans = MIN(ans, MAX(x[2]-x[1], x[4]-x[3]));
continue;
}
col= j;
a=0;
b=h-1;
dp2.insert({-1, x[1], x[2], MIN(x[3], min_tree()), MAX(x[4], max_tree())});
min=x[1];
max=x[2];
for(int i = 0; i<=limit; ++i){
min = MIN(min, mat[i][j]);
max = MAX(max, mat[i][j]);
a=i+1;
dp2.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
}
}
dp.clear();
dp=dp2;
dp2.clear();
}
//std::cout << "prelim: " << ans <<'\n';
dp.clear();
dp.insert({-1, 2000123000, 0, 2000123000, 0});
for(int j = 0; j<=w; ++j){
for(std::vector<int> x : dp){
//limit, min, max, min, max
/*
std::cout << j<<"pos ";
for(int c : x){
std::cout << c <<' ';
}
std::cout <<'\n';
//*/
limit=x[0];
if(j==w){
ans = MIN(ans, MAX(x[2]-x[1], x[4]-x[3]));
continue;
}
col= j;
a=0;
b=h-1;
//dp2.insert({-1, x[1], x[2], MIN(x[3], min_tree()), MAX(x[4], max_tree())});
min=x[1];
max=x[2];
for(int i = 0; i<limit; ++i){
min = MIN(min, mat[i][j]);
max = MAX(max, mat[i][j]);
}
for(int i = limit; i<h; ++i){
if(i>=0){
min = MIN(min, mat[i][j]);
max = MAX(max, mat[i][j]);
}
//std::cout <<min <<':' << max <<'\n';
a=i+1;
if(a<h){
dp2.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
}
else{
dp2.insert({i, min, max, x[3], x[4]});
}
}
}
dp.clear();
dp=dp2;
dp2.clear();
}
std::cout << ans;
return 0;
}