Submission #51007

#	Time	Username	Problem	Language	Result	Execution time	Memory
51007		Diuven	The Kingdom of JOIOI (JOI17_joioi)	C++11	100 / 100	3849 ms	167540 KiB

joioi

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long lld;
const int MX=2010, inf=2e9;

inline int _max(int x, int y){ return x>y ? x : y; }
inline int _min(int x, int y){ return x<y ? x : y; }

int B[MX][MX];
int w, h;

struct node {
    int val, x, y;
    bool used;
};

int D[MX][MX];

node V[MX*MX];

int solve(){

    int hi=0;
    for(int i=1, idx=0; i<=h; i++)
        for(int j=1; j<=w; j++){
            V[idx++]={B[i][j], i, j, false};
            hi=_max(hi, B[i][j]);
        }

    sort(V, V+h*w, [](node &a, node &b){
        if(a.val==b.val){
            if(a.x==b.x) return a.y<b.y;
            return a.x<b.x;
        }
        return a.val<b.val;
    });
    for(int i=0; i<h*w; i++){
        node &nd=V[i];
        D[nd.x][nd.y]=i;
    }

    int pos[MX]={}; pos[0]=w;
    int mn=inf, mx=0, ans=inf, cnt=0;

    for(int idx=0, nah=0; idx<h*w; idx++){
        int val=V[idx].val, i=V[idx].x;
        for(; i<=h; i++){
            bool uptd=false;
            while(pos[i]<pos[i-1] && B[i][pos[i]+1]<=val){
                uptd=true; pos[i]++;
                int now=B[i][pos[i]];
                mn=_min(mn, now), mx=_max(mx, now);
                V[D[i][pos[i]]].used=true;
                cnt++;
            }
            if(!uptd) break;
        }

        if(cnt==0 || cnt==w*h) continue;
        while(nah<=w*h-1 && V[nah].used) nah++;
        ans=_min(ans, _max(mx-mn, hi-V[nah].val) );
    }
    return ans;
}

void flip_v(){
    for(int i=1; i<=h/2; i++)
        for(int j=1; j<=w; j++)
            swap(B[i][j], B[h-i+1][j]);
}

void flip_h(){
    for(int i=1; i<=h; i++)
        for(int j=1; j<=w/2; j++)
            swap(B[i][j], B[i][w-j+1]);
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>h>>w;
    for(int i=1; i<=h; i++)
        for(int j=1; j<=w; j++)
            cin>>B[i][j];
    int ans=solve();
    flip_v();
    ans=min(ans, solve());
    flip_h();
    ans=min(ans, solve());
    flip_v();
    ans=min(ans, solve());
    cout<<ans;
    return 0;
}

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