Submission #1365302

#TimeUsernameProblemLanguageResultExecution timeMemory
1365302AvianshText editor (CEOI24_editor)C++20
100 / 100
73 ms31552 KiB
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int inf = 2e18;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    int sl,sc;
    cin >> sl >> sc;
    sl--;
    sc--;
    int el,ec;
    cin >> el >> ec;
    el--;
    ec--;
    int arr[n];
    for(int &i : arr){
        cin >> i;
        ++i;
    }
    int mns[n];
    mns[sl]=arr[sl];
    for(int i = sl-1;i>=0;i--){
        mns[i]=min(mns[i+1],arr[i]);
    }
    for(int i = sl+1;i<n;i++){
        mns[i]=min(mns[i-1],arr[i]);
    }

    int mne[n];
    mne[el]=arr[el];
    for(int i = el-1;i>=0;i--){
        mne[i]=min(mne[i+1],arr[i]);
    }
    for(int i = el+1;i<n;i++){
        mne[i]=min(mne[i-1],arr[i]);
    }
    int ans = inf;
    //Case 1:
    for(int i = 0;i<n;i++){
        //start -> i -> end
        int col = min({mns[i]-1,mne[i]-1,sc});
        ans=min(ans,abs(i-sl)+abs(i-el)+abs(ec-col));
    }
    //Case 2:
    int dists[n];
    fill(dists,dists+n,inf);
    for(int i = 0;i<n;i++){
        int col = min(mns[i]-1,sc);
        dists[i]=min(dists[i],abs(i-sl)+col);
        if(i<n-1){
            dists[i+1]=abs(i-sl)+(arr[i]-col);
        }
    }
    for(int i = 1;i<n;i++){
        dists[i]=min(dists[i],dists[i-1]+1);
    }
    for(int i = n-2;i>=0;i--){
        dists[i]=min(dists[i],dists[i+1]+1);
    }
    for(int i = 1;i<n;i++){
        ans=min(ans,dists[i]+1+abs((i-1)-el)+abs(mne[i-1]-1-ec));
    }
    ans=min(ans,dists[el]+ec);
    cout << ans;
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...