#include <bits/stdc++.h>
using namespace std;
#define int long long
template<class A, class B>
bool chmin(A &a, const B &b) {
return a > b ? (a = b) == b : false;
} template<class A, class B>
bool chmax(A &a, const B &b) {
return a < b ? (a = b) == b : false;
}
const int inf = 1e18;
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n; cin >> n;
int sl, sc; cin >> sl >> sc;
int el, ec; cin >> el >> ec;
int l[n + 1];
for (int i = 1; i <= n; ++i) {
cin >> l[i];
l[i]++;
}
if (n == 1) {
if (sc == ec) cout << 0;
else cout << 1;
return 0;
}
if (sl > el) {
swap(sl, el);
swap(sc, ec);
}
vector<vector<int>> dp(n + 1, vector<int> (3, inf));
vector<int> p(n + 1);
dp[sl][0] = sc - 1;
dp[sl][1] = l[sl] - sc;
dp[sl][2] = 0; p[sl] = sc;
if (sl + 1 <= n) chmin(dp[sl][0], dp[sl][1] + 2);
if (sl - 1 >= 1) chmin(dp[sl][0], dp[sl][2] + max(l[sl - 1] - p[sl], 0ll) + 2);
if (sl + 1 <= n) chmin(dp[sl][1], dp[sl][0] + 2);
if (sl - 1 >= 1) chmin(dp[sl][1], dp[sl][0] + max(l[sl] - l[sl - 1], 0ll) + 2);
for (int i = sl + 1; i <= el; ++i) {
dp[i][0] = min(dp[i - 1][0] + 1, dp[i - 1][1] + 1);
chmin(dp[i][0], dp[i - 1][2] + min(l[i], p[i - 1]));
dp[i][1] = dp[i - 1][0] + l[i];
chmin(dp[i][1], dp[i - 1][1] + max(l[i] - l[i - 1], 0ll) + 1);
chmin(dp[i][1], dp[i - 1][2] + max(l[i] - p[i - 1], 0ll) + 1);
chmin(dp[i][0], dp[i][1] + l[i] - 1);
chmin(dp[i][1], dp[i][0] + l[i] - 1);
dp[i][2] = dp[i - 1][2] + 1;
p[i] = min(l[i], p[i - 1]);
if (chmin(dp[i][2], dp[i][0])) p[i] = 1;
if (chmin(dp[i][2], dp[i][1])) p[i] = l[i];
chmin(dp[i][0], dp[i][2] + p[i] - 1);
chmin(dp[i][1], dp[i][2] + l[i] - p[i]);
if (i + 1 <= n) chmin(dp[i][0], dp[i][1] + 2);
if (i - 1 >= 1) chmin(dp[i][0], dp[i][2] + max(l[i - 1] - p[i], 0ll) + 2);
if (i + 1 <= n) chmin(dp[i][1], dp[i][0] + 2);
if (i - 1 >= 1) chmin(dp[i][1], dp[i][0] + max(l[i] - l[i - 1], 0ll) + 2);
}
int res = min({dp[el][0] + ec - 1, dp[el][1] + l[el] - ec, dp[el][2] + abs(p[el] - ec)});
if (el - 1 >= 1) {
chmin(res, dp[el][0] + 1 + abs(l[el - 1] - ec));
chmin(res, dp[el - 1][1] + ec);
if (l[el - 1] <= l[el]) chmin(res, dp[el - 1][1] + abs(l[el - 1] - ec) + 1);
if (p[el - 1] <= l[el]) chmin(res, dp[el - 1][2] + abs(p[el - 1] - ec) + 1);
}
cout << res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |