제출 #756311

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
756311		1bin	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	2173 ms	94792 KiB

joioi

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 2005;
struct p{
    int x, y, d, f;
    bool operator<(const p & t)const{return d > t.d;}
};
int h, w, a[NMAX][NMAX], ans, mx, mn, L[NMAX], R[NMAX], b[NMAX][NMAX];
vector<p> v;

void rotate(){
    for(int i = 1; i <= h; i++)
        for(int j = 1; j <= w; j++)
            b[j][h + 1 - i] = a[i][j];
    swap(w, h);
    for(int i = 1; i <= h; i++) 
        for(int j = 1; j <= w; j++) a[i][j] = b[i][j];
    return;
}

int solve(){
    v.clear();
    memset(R, 0x3f, sizeof(R));
    memset(L, 0, sizeof(L));
    for(int i = 1; i <= h; i++)
        for(int j = 1; j <= w; j++) {
            int d = max(mx - a[i][j], a[i][j] - mn);
            int f = (d == a[i][j] - mn);
            v.push_back({j, i, d, f});
        }
    sort(all(v));

    for(auto&t : v){
        int x = t.x, y = t.y, d = t.d, f = t.f;
        if(f){
            int r = max(x, L[y]);
            for(int i = y; i <= h; i++){
                if(L[i] >= r) break;
                L[i] = r;
                if(R[i] <= r) return d;
            }
        }
        else{
            R[y] = min(R[y], x);
            if(L[y] >= R[y]) return d;
        }
    }
    int val = a[v.back().y][v.back().x];
    return min(val - mn, mx - val);
}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    ans = mn = 2e9;
    cin >> h >> w;
    for(int i = 1; i <= h; i++)
        for(int j = 1; j <= w; j++) {
            cin >> a[i][j];
            mx = max(mx, a[i][j]);
            mn = min(mn, a[i][j]);
        }
    
    for(int _ = 0; _ < 4; _++){
        ans = min(ans, solve());
        rotate();
    }
    cout << ans;
    return 0;
}

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