제출 #1342810

#제출 시각아이디문제언어결과실행 시간메모리
1342810po_rag526Text editor (CEOI24_editor)C++20
0 / 100
1 ms344 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 2000000000
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]++;
    }
    if (sl > el){
        swap(sl, el), swap(sc, ec);
        for (int i = 1; i <= n / 2; i++){
            swap(v[i], v[n - i + 1]);
        }
    }
    ll ans = INF;
    ll mi = sc;
    for (int i = sl; i <= el; i++){
        mi = min(v[i], mi);
    }
    ans = min(ans, abs(mi - ec) + abs(sl - el));
    ll cur = mi;
    for (int i = sl; i >= 1; i--){
        cur = min(mi, v[i]);
        ans = min(ans, abs(sl - i) + abs(el - i) + abs(cur - ec));
    }
    cur = mi;
    for (int i = el; i <= n; i++){
        cur = min(mi, v[i]);
        ans = min(ans, abs(sl - i) + abs(el - i) + abs(cur - ec));
    }

    vector<ll> co1(n + 1, INF);
    cur = sc;
    for (int i = sl; i <= n; i++){
        cur = min(cur, v[i]);
        co1[i] = min(co1[i], abs(sl - i) + cur - 1);
        if (i != n){
            co1[i + 1] = min(co1[i + 1], abs(sl - i) + v[i] - cur + 1);
        }
    }
    for (int i = sl; i >= 1; i--){
        cur = min(cur, v[i]);
        co1[i] = min(co1[i], abs(sl - i) + cur - 1);
        if (i != n){
            co1[i + 1] = min(co1[i + 1], abs(sl - i) + v[i] - cur + 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]);
    }
    vector<ll> en(n + 1, INF);
    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...