Submission #669560

#	Time	Username	Problem	Language	Result	Execution time	Memory
669560		Dec0Dedd	The Kingdom of JOIOI (JOI17_joioi)	C++14	60 / 100	4067 ms	176796 KiB

joioi

#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, short>

const int N = 2e3+110;
const int INF = 1e9;

int a[N][N], cnt[N], h, w;
vector<int> v;

int solve() {
    memset(cnt, 0, sizeof(cnt));

    int res=INF;
    multiset<int> js, is;

    for (int i=1; i<=h; ++i) {
        for (int j=1; j<=w; ++j) js.insert(a[i][j]); 
    }

    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({a[1][w], w});

    for (int k=0; k<(int)v.size(); ++k) {
        while (!pq.empty()) {
            if (pq.top().first <= v[k]) {
                pii x=pq.top(); pq.pop();
                js.erase(js.find(x.first)), is.insert(x.first);
                ++cnt[x.second];
                if (cnt[x.second] == h) continue;

                if (x.second == w || cnt[x.second+1] >= cnt[x.second]+1) {
                    pq.push({a[cnt[x.second]+1][x.second], x.second});
                }

                if (x.second == 1) continue;
                if (cnt[x.second] == cnt[x.second-1]+1) {
                    pq.push({a[cnt[x.second]][x.second-1], x.second-1});
                }
            } else break;
        }

        int lf, rf;
        if (js.empty()) lf=INF;
        else lf=(*js.rbegin())-(*js.begin());

        if (is.empty()) rf=INF;
        else rf=(*is.rbegin())-(*is.begin());

        res=min(res, max(lf, rf));
    }

    return res;
}

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

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>h>>w;

    for (int i=1; i<=h; ++i) {
        for (int j=1; j<=w; ++j) {
            cin>>a[i][j];
            v.push_back(a[i][j]);
        }
    } sort(v.begin(), v.end());

    v.erase(unique(v.begin(), v.end()), v.end());
    int ans=solve();
    hor(); ans=min(ans, solve()); hor();

    ver();
    ans=min(ans, solve());
    hor(); ans=min(ans, solve()); hor();
    cout<<ans<<"\n";
}

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