Submission #1195379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195379		Turkhuu	Text editor (CEOI24_editor)	C++20	16 / 100	125 ms	63120 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;
    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);
    }
    ll best = 1e18; mn = 1e18;
    FOR(i, tx, n - 1) best = min(best, 2 * i + abs((mn = min(mn, a[i])) - ty));
    ll mn2 = 1e18; mn = 1e18;
    ROF(i, tx, 0) {
        mn = min(mn, a[i]);
        mn2 = min(mn2, dis[i][1] + i);
        if (mn <= ty) ans = min(ans, mn2 - i + tx - i + ty - mn);
        else ans = min(ans, dis[i][1] + best - tx - i);
    }
    best = mn = 1e18;
    FOR(i, 0, tx) best = min(best, -2 * i + abs((mn = min(mn, a[i])) - ty));
    mn2 = mn = 1e18;
    FOR(i, tx, n - 1) {
        mn = min(mn, a[i]);
        mn2 = min(mn2, dis[i][1] - i);
        if (mn <= ty) ans = min(ans, mn2 + i + i - tx + ty - mn);
        else ans = min(ans, dis[i][1] + best + tx + i);
    }
    FOR(i, 0, n - 1) ans = min(ans, dis[i][0] + abs(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: 11 / 11
• Subtask 5: 0 / 44