Submission #1195310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195310		Turkhuu	Text editor (CEOI24_editor)	C++20	5 / 100	4101 ms	198000 KiB

Main

#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i = (a); i <= (b); i++)
#define ROF(i, a, b) for (auto i = (a); i >= (b); i--)
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; ll sx, sy, tx, ty;
    cin >> n >> sx >> sy >> tx >> ty;
    sx--, sy--, tx--, ty--;
    vector<ll> a(n);
    for (auto& x : a) cin >> x;
    auto s = a;
    s.push_back(sy);
    s.push_back(ty);
    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end());
    int m = s.size();
    map<ll, int> id;
    FOR(i, 0, m - 1) id[s[i]] = i;
    auto engiin = [&](ll x1, ll y1, ll x2, ll y2) -> ll {
        vector dis(n, vector<ll>(m, 1e18));
        priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> pq;
        for (pq.push({dis[x1][id[y1]] = 0, x1, id[y1]}); !pq.empty(); pq.pop()) {
            auto [d, x, _y] = pq.top();
            if (d != dis[x][_y]) continue;
            ll y = s[_y];
            vector<array<ll, 3>> moves;
            if (x) {
                moves.push_back({x - 1, id[min(a[x - 1], y)], 1});
                moves.push_back({x - 1, id[a[x - 1]], y + 1});
            }
            if (x + 1 < n) {
                moves.push_back({x + 1, id[min(a[x + 1], y)], 1});
                moves.push_back({x + 1, id[0], a[x] - y + 1});
            }
            for (auto [u, v, w] : moves) if (d + w < dis[u][v]) pq.push({dis[u][v] = d + w, u, v});
        }
        ll ans = 1e18;
        FOR(i, 0, m - 1) ans = min(ans, dis[x2][i] + abs(s[i] - y2));
        return ans;
    };
    vector dis(n, vector<ll>(2));
    FOR(i, 0, n - 1) dis[i] = {engiin(sx, sy, i, 0), engiin(sx, sy, i, a[i])};
    priority_queue<array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pq;
    FOR(i, 0, n - 1) {
        if (i) dis[i][0] = min(dis[i][0], dis[i - 1][1] + 1);
        pq.push({dis[i][0], i});
    }
    for (; !pq.empty(); pq.pop()) {
        auto [d, i] = pq.top();
        if (d != dis[i][0]) continue;
        if (i) pq.push({d + 1, i - 1});
        if (i + 1 < n) pq.push({d + 1, i + 1});
    }
    FOR(i, 0, n - 2) dis[i][1] = min(dis[i][1], dis[i + 1][0] + 1);
    ll ans = engiin(sx, sy, tx, ty);
    FOR(i, 0, n - 1) {
        ans = min(ans, dis[i][0] + engiin(i, 0, tx, ty));
        ans = min(ans, dis[i][1] + engiin(i, a[i], tx, ty));
    }
    cout << ans << "\n";
    return 6/22;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 26
• Subtask 4: 0 / 11
• Subtask 5: 0 / 44