Submission #1195372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195372		Turkhuu	Text editor (CEOI24_editor)	C++20	45 / 100	4096 ms	55364 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 engiin = [&](ll x1, ll y1, ll x2, ll y2) -> ll {
        ll y = y1, p = min(x1, x2), q = max(x1, x2);
        FOR(i, p, q) y = min(y, a[i]);
        ll ans = q - p + abs(y - y2);
        if (y <= y2) return ans;
        ROF(i, p - 1, 0) {
            ans = min(ans, x1 - i + x2 - i + abs(a[i] - y2));
            if (a[i] <= y2) break;
        }
        FOR(i, q + 1, n - 1) {
            ans = min(ans, i - x2 + i - x1 + abs(a[i] - y2));
            if (a[i] <= y2) break;
        }
        return ans;
    };
    ll mnst = sy;
    FOR(i, min(sx, tx), max(sx, tx)) mnst = min(mnst, a[i]);
    vector dis(n, vector<ll>(2));
    FOR(i, 0, n - 1) dis[i][0] = abs(i - sx) + min(sy, a[i]);
    ll mn = sy, ans = abs(sx - tx) + abs(mnst - ty);
    ROF(i, sx - 1, 0) {
        dis[i][1] = sx - i + a[i] - (mn = min(mn, a[i]));
        if (i <= tx) ans = min(ans, sx - i + tx - i + abs(min(mnst, mn) - ty));
    }
    mn = sy;
    FOR(i, sx, n - 1) {
        dis[i][1] = i - sx + a[i] - (mn = min(mn, a[i]));
        if (i >= tx) ans = min(ans, i - sx + i - tx + abs(min(mnst, mn) - ty));
    }
    FOR(i, 1, n - 1) dis[i][0] = min(dis[i][0], min(dis[i - 1][0], dis[i - 1][1]) + 1);
    ROF(i, n - 2, 0) {
        dis[i][0] = min(dis[i][0], dis[i + 1][0] + 1);
        dis[i][1] = min(dis[i][1], dis[i + 1][0] + 1);
    }
    FOR(i, 0, n - 1) {
        ans = min(ans, dis[i][0] + abs(i - 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: 14 / 14
• Subtask 3: 26 / 26
• Subtask 4: 0 / 11
• Subtask 5: 0 / 44