제출 #1137579

#제출 시각아이디문제언어결과실행 시간메모리
1137579Sir_Ahmed_ImranText editor (CEOI24_editor)C++20
16 / 100
83 ms12100 KiB
                //    01001100 01001111 01010100 01000001    \\
                //                                           \\
                //                ╦  ╔═╗╔╦╗╔═╗               \\
                //                ║  ║ ║ ║ ╠═╣               \\
                //                ╩═╝╚═╝ ╩ ╩ ╩               \\
                //                                           \\
                //    01001100 01001111 01010100 01000001    \\

#include <bits/stdc++.h>
using namespace std;

#define N 1000001
#define nl '\n'
#define ff first
#define ss second
#define add insert
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

int l[N];
int dp[N][2];

void solve(){
    int n, m, sl, sc, el, ec, ans;
    cin >> n >> sl >> sc >> el >> ec;
    sc --, ec --;
    for (int i = 1; i <= n; i++)
        cin >> l[i];
    m = sc;
    for (int i = sl; i > 0; i--){
        m = min(m, l[i]);
        dp[i][0] = sl - i + m;
        dp[i][1] = sl - i + l[i] - m;
        if(i == el)
            ans = sl - i + abs(m - ec);
    }
    for (int i = sl; i <= n; i++){
        m = min(m, l[i]);
        dp[i][0] = i - sl + m;
        dp[i][1] = i - sl + l[i] - m;
        if(i == el)
            ans = i - sl + abs(m - ec);
    }
    for (int i = 1; i < n; i++){
        dp[i + 1][0] = min(dp[i + 1][0], min(dp[i][0], dp[i][1]) + 1);
        dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + 1 + max(0, l[i + 1] - l[i])); 
    }
    for (int i = n; i > 1; i--){
        dp[i - 1][0] = min(dp[i - 1][0], dp[i][0] + 1);
        dp[i - 1][1] = min(dp[i - 1][1], dp[i][0] + 1);
        dp[i - 1][1] = min(dp[i - 1][1], dp[i][1] + 1 + max(0, l[i - 1] - l[i])); 
    }
    for (int i = 1; i < n; i++){
        dp[i + 1][0] = min(dp[i + 1][0], min(dp[i][0], dp[i][1]) + 1);
        dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + 1 + max(0, l[i + 1] - l[i])); 
    }
    for (int i = n; i > 1; i--){
        dp[i - 1][0] = min(dp[i - 1][0], dp[i][0] + 1);
        dp[i - 1][1] = min(dp[i - 1][1], dp[i][0] + 1);
        dp[i - 1][1] = min(dp[i - 1][1], dp[i][1] + 1 + max(0, l[i - 1] - l[i])); 
    }
    for (int i = 1; i < n; i++){
        dp[i + 1][0] = min(dp[i + 1][0], min(dp[i][0], dp[i][1]) + 1);
        dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + 1 + max(0, l[i + 1] - l[i])); 
    }
    for (int i = n; i > 1; i--){
        dp[i - 1][0] = min(dp[i - 1][0], dp[i][0] + 1);
        dp[i - 1][1] = min(dp[i - 1][1], dp[i][0] + 1);
        dp[i - 1][1] = min(dp[i - 1][1], dp[i][1] + 1 + max(0, l[i - 1] - l[i])); 
    }
    for (int i = 1; i < n; i++){
        dp[i + 1][0] = min(dp[i + 1][0], min(dp[i][0], dp[i][1]) + 1);
        dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + 1 + max(0, l[i + 1] - l[i])); 
    }
    for (int i = n; i > 1; i--){
        dp[i - 1][0] = min(dp[i - 1][0], dp[i][0] + 1);
        dp[i - 1][1] = min(dp[i - 1][1], dp[i][0] + 1);
        dp[i - 1][1] = min(dp[i - 1][1], dp[i][1] + 1 + max(0, l[i - 1] - l[i])); 
    }
    m = l[el];
    ans = min(ans, dp[el][0] + ec);
    for (int i = el; i > 0; i--){
        m = min(m, l[i]);
        ans = min(ans, dp[i][1] + el - i + abs(m - ec));
    }
    m = l[el];
    for (int i = el; i <= n; i++){
        m = min(m, l[i]);
        ans = min(ans, dp[i][1] + i - el + abs(m - ec));
    }
    cout << ans;
}

int terminator(){
    L0TA;
    solve();
    return 0;
}
#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...