Submission #1342878

#TimeUsernameProblemLanguageResultExecution timeMemory
1342878HasanV11010238Text editor (CEOI24_editor)C++20
45 / 100
277 ms20852 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 2000000000000
int main(){
    ll n, sl, sc, el, ec;
    cin>>n;
    cin>>sl>>sc;
    cin>>el>>ec;
    vector<ll> v(n + 1, 0);
    for (int i = 1; i <= n; i++){
        cin>>v[i];
        v[i]++;
    }
    ll ans = INF;
    ll mi = sc;
    for (int i = min(sl, el); i <= max(sl, el); i++){
        mi = min(v[i], mi);
    }
    ans = min(ans, abs(mi - ec) + abs(sl - el));
    ll cur = mi;
    for (int i = min(sl, el); i >= 1; i--){
        cur = min(cur, v[i]);
        ans = min(ans, abs(sl - i) + abs(el - i) + abs(cur - ec));
    }
    cur = mi;
    for (int i = max(sl, el); i <= n; i++){
        cur = min(cur, v[i]);
        ans = min(ans, abs(sl - i) + abs(el - i) + abs(cur - ec));
    }
    vector<ll> en(n + 1, INF);
    vector<ll> co1(n + 1, INF);
    cur = sc;
    for (int i = sl; i <= n; i++){
        cur = min(cur, v[i]);
        en[i] = min(en[i], v[i] - cur + abs(sl - i));
        co1[i] = min(co1[i], abs(sl - i) + cur - 1);
        if (i != n){
            co1[i + 1] = min(co1[i + 1], abs(sl - i) + max(v[i] - cur, 0LL) + 1);
        }
    }
    cur = sc;
    for (int i = sl; i >= 1; i--){
        cur = min(cur, v[i]);
        en[i] = min(en[i], v[i] - cur + abs(sl - i));
        co1[i] = min(co1[i], abs(sl - i) + cur - 1);
        if (i != n){
            co1[i + 1] = min(co1[i + 1], abs(sl - i) + max(v[i] - cur, 0LL) + 1);
        }
    }
    for (int i = 1; i <= n; i++){
        co1[i] = min(co1[i], co1[i - 1] + 1);
    }
    for (int i = n - 1; i >= 1; i--){
        co1[i] = min(co1[i], co1[i + 1] + 1);
    }
    for (int i = 1; i <= n; i++){
        ans = min(ans, abs(el - i) + ec - 1 + co1[i]);
    }
    for (int i = 1; i <= n; i++){
        en[i] = min(en[i], min(co1[i + 1] + 1, co1[i] + v[i] - 1));
    }
    mi = INF;
    for (int i = el; i <= n; i++){
        mi = min(mi, v[i]);
        ans = min(ans, en[i] + abs(i - el) + abs(mi - ec));
    }
    mi = INF;
    for (int i = el; i >= 1; i--){
        mi = min(mi, v[i]);
        ans = min(ans, en[i] + abs(i - el) + abs(mi - ec));
    }
    cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...