oj.uz

Submission #669559

# Submission time Handle Problem Language Result Execution time Memory
669559 2022-12-06T18:27:30 Z Dec0Dedd The Kingdom of JOIOI (JOI17_joioi) C++14
60 / 100
 4000 ms 230544 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair<ll, short>

const int N = 2e3+110;
const ll INF = 1e18;

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

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

    ll 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;
        }

        ll 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());
    ll 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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 328 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 3 ms 468 KB Output is correct
16 Correct 74 ms 3540 KB Output is correct
17 Correct 103 ms 3900 KB Output is correct
18 Correct 97 ms 3920 KB Output is correct
19 Correct 101 ms 3924 KB Output is correct
20 Correct 89 ms 3532 KB Output is correct
21 Correct 104 ms 4112 KB Output is correct
22 Correct 103 ms 3956 KB Output is correct
23 Correct 100 ms 3992 KB Output is correct
24 Correct 84 ms 3632 KB Output is correct
25 Correct 102 ms 3940 KB Output is correct
26 Correct 105 ms 4048 KB Output is correct
27 Correct 109 ms 3972 KB Output is correct
28 Correct 108 ms 4020 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 3 ms 468 KB Output is correct
16 Correct 74 ms 3540 KB Output is correct
17 Correct 103 ms 3900 KB Output is correct
18 Correct 97 ms 3920 KB Output is correct
19 Correct 101 ms 3924 KB Output is correct
20 Correct 89 ms 3532 KB Output is correct
21 Correct 104 ms 4112 KB Output is correct
22 Correct 103 ms 3956 KB Output is correct
23 Correct 100 ms 3992 KB Output is correct
24 Correct 84 ms 3632 KB Output is correct
25 Correct 102 ms 3940 KB Output is correct
26 Correct 105 ms 4048 KB Output is correct
27 Correct 109 ms 3972 KB Output is correct
28 Correct 108 ms 4020 KB Output is correct
29 Execution timed out 4035 ms 230544 KB Time limit exceeded
30 Halted 0 ms 0 KB -