제출 #241271

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
241271		aggu_01000101	The Kingdom of JOIOI (JOI17_joioi)	C++14	0 / 100	5 ms	256 KiB

joioi

#include <bits/stdc++.h>
#define int long long
#define mid(l, u) ((l+u)/2)
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
#define INF 100000000000
using namespace std;
const int N = 2005;
int n, m;
int mat[N][N];
pair<int, int> pmm[N][N];
int ourmin, ourmax;
int ind[N];
int ans = 0;
int mini = 0, maxi = INF;
set<int> el;
vector<int> dist;
void calcpmm(){
    for(int i =0 ;i<n;i++){
        pmm[i][m-1] = {mat[i][m-1], mat[i][m-1]};
        for(int j = m-2;j>=0;j--){
            pmm[i][j].first = min(mat[i][j], pmm[i][j+1].first);
            pmm[i][j].second = max(mat[i][j], pmm[i][j+1].second);
        }
    }
}
int findinrange(int l, int u){
    //cout<<endl;
    //cout<<l<<" "<<u<<endl;
    /*for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++) cout<<mat[i][j]<<" ";
        cout<<endl;
    }*/
    int theirmin = INF;
    int theirmax = -INF;
    bool canmove = true;
    for(int i =0 ;i<n;i++){
        int j = ind[i];
        if(canmove) {
            for (; j < m && mat[i][j] >= l && mat[i][j] <= u; j++) {
                ourmin = min(mat[i][j], ourmin);
                ourmax = max(ourmax, mat[i][j]);
            }
        }
        if(j==0){
            if(i==0) return INF;
            canmove = false;
        }
        if(j<m){
            theirmin = min(pmm[i][j].first, theirmin);
            theirmax = max(pmm[i][j].second, theirmax);
        }
    }
    if(ourmin > ourmax || theirmin > theirmax) return INF;
    //cout<<theirmax<<" "<<theirmin<<" "<<ourmax<<" "<<ourmin<<endl;
    //cout<<max(theirmax - theirmin, ourmax - ourmin)<<endl;
    //cout<<endl;
    return max(theirmax - theirmin, ourmax - ourmin);
}
int findans(){
    /*for(int i =0 ;i<n;i++){
        for(int j = 0;j<m;j++) cout<<mat[i][j]<<" ";
        cout<<endl;
    }
    cout<<endl<<endl;*/
    calcpmm();
    int tr = INF;
    for(int i = 0;i<n;i++){
        ind[i] = 0;
    }
    ourmin = INF;
    ourmax = -INF;
    int l = mini;
    for(int u: dist){
        if(u==maxi) break;
        tr = min(tr, findinrange(l, u));
    }
    ourmin = INF;
    ourmax = -INF;
    int u = maxi;
    for(int i = 0;i<n;i++) ind[i] = 0;
    for(int k = dist.size()-1;k>0;k--){
        tr = min(tr, findinrange(dist[k], u));
    }
    return tr;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m;
    int a[n][m];
    for(int i =0 ;i<n;i++){
        for(int j = 0;j<m;j++) {
            cin >> mat[i][j];
            maxi = max(maxi, mat[i][j]);
            mini = min(mini, mat[i][j]);
            a[i][j] = mat[i][j];
            el.insert(mat[i][j]);
        }
    }
    for(int j: el) dist.push_back(j);
    ans = maxi - mini;
    ans = min(ans, findans());
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++) mat[i][j] = a[i][m-j-1];
    }
    ans = min(ans, findans());
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++) mat[i][j] = a[n-i-1][m-j-1];
    }
    ans = min(ans, findans());
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++) mat[i][j] = a[n-i-1][j];
    }
    ans = min(ans, findans());
    cout<<ans<<endl;
}
/*

4 4
1 12 6 11
11 10 2 14
10 1 9 20
4 17 19 10


8 6
23 23 10 11 16 21
15 26 19 28 19 20
25 26 28 16 15 11
11 8 19 11 15 24
14 19 15 14 24 11
10 8 11 7 6 14
23 5 19 23 17 17
18 11 21 14 20 16
 */

• Subtask 1: 0 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40