Submission #1193005

#TimeUsernameProblemLanguageResultExecution timeMemory
1193005mmaitiText editor (CEOI24_editor)C++20
5 / 100
1 ms328 KiB
#include <bits/stdc++.h>
#include <climits>
using namespace std;
typedef long long ll;
#define vi vector<int>
#define si set<int>
#define usi unordered_set<int>
#define sll set<ll>
#define usll unordered_set<ll>
#define vb vector<bool>
#define vll vector<ll>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vvi vector<vector<int>>
#define vvll vector<vector<ll>>

void solve() {
  ll N;
  cin >> N;
  pll st, en;
  cin >> st.first >> st.second >> en.first >> en.second;
  --st.first;
  --st.second;
  --en.first;
  --en.second;
  vll L(N);
  for (int i = 0; i < N; i++) {

    cin >> L[i];
    L[i]++;
  }
  // walk takes care of getting to fx, fy from ix, iy
  // it doesn't use any left special or right speical, but
  // it can use up special and down special
  auto walk = [&](ll ix, ll iy, ll targx, ll targy) {
    if (ix >= targx) {
      for (int cur = ix; cur > targx; cur--) {
        if (iy >= L[cur - 1] - 1) {
          iy = L[cur - 1] - 1;
        }
      }
    } else {
      for (int cur = ix; cur < targx; cur++) {
        if (iy >= L[cur + 1] - 1) {
          iy = L[cur + 1] - 1;
        }
      }
    }
    return abs(iy - targy) + abs(ix - targx);
  };
  ll ans = LLONG_MAX;
  ans = min(ans, walk(st.first, st.second, en.first, en.second));
  if (st.second <= en.second) {
    // in this case we assume we only need to use the left jumps
    for (int i = N - 1; i >= 1; i--) {
      ans = min(ans, walk(st.first, st.second, i, 0) + 1 +
                         walk(i - 1, L[i - 1] - 1, en.first, en.second));
    }
  } else {
    // in this case we assume we only need to use the right jumps
    for (int i = 0; i < N; i++) {
      ans = min(ans, walk(st.first, st.second, i, L[i] - 1) + 1 +
                         walk(i + 1, 0, en.first, en.second));
    }
  }
  cout << ans << "\n";
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  solve();
}
#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...