oj.uz

Submission #50322

# Submission time Handle Problem Language Result Execution time Memory
50322 2018-06-10T06:28:38 Z 노영훈(#1281, Diuven) The Kingdom of JOIOI (JOI17_joioi) C++11
0 / 100
 2 ms 488 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long lld;
const int MX=2010, inf=2e9;

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

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

int D[MX][MX];

int solve(){
    vector<node> V;

    int hi=0;
    for(int i=1; i<=h; i++)
        for(int j=1; j<=w; j++){
            V.push_back({B[i][j], i, j});
            hi=max(hi, B[i][j]);
        }

    sort(V.begin(), V.end(), [](node &a, node &b){
        if(a.val==b.val)
            return pii(a.x,a.y) < pii(b.x,b.y);
        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 && V[nah+1].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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Incorrect 2 ms 488 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Incorrect 2 ms 488 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Incorrect 2 ms 488 KB Output isn't correct
4 Halted 0 ms 0 KB -