Submission #1195312

#TimeUsernameProblemLanguageResultExecution timeMemory
1195312TurkhuuText editor (CEOI24_editor)C++20
45 / 100
4019 ms55284 KiB
#include <bits/stdc++.h> #define FOR(i, a, b) for (auto i = (a); i <= (b); i++) #define ROF(i, a, b) for (auto i = (a); i >= (b); i--) using namespace std; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; ll sx, sy, tx, ty; cin >> n >> sx >> sy >> tx >> ty; sx--, sy--, tx--, ty--; vector<ll> a(n); for (auto& x : a) cin >> x; auto engiin = [&](ll x1, ll y1, ll x2, ll y2) -> ll { ll y = y1, p = min(x1, x2), q = max(x1, x2); FOR(i, p, q) y = min(y, a[i]); ll ans = q - p + abs(y - y2), mn = y; ROF(i, p - 1, 0) { mn = min(mn, a[i]); ans = min(ans, x1 - i + x2 - i + abs(mn - y2)); } mn = y; FOR(i, q + 1, n - 1) { mn = min(mn, a[i]); ans = min(ans, i - x2 + i - x1 + abs(mn - y2)); } return ans; }; vector dis(n, vector<ll>(2)); FOR(i, 0, n - 1) dis[i] = {engiin(sx, sy, i, 0), engiin(sx, sy, i, a[i])}; // priority_queue<array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pq; FOR(i, 0, n - 1) { if (i) dis[i][0] = min(dis[i][0], dis[i - 1][1] + 1); // pq.push({dis[i][0], i}); } // for (; !pq.empty(); pq.pop()) { // auto [d, i] = pq.top(); // if (d != dis[i][0]) continue; // if (i) pq.push({d + 1, i - 1}); // if (i + 1 < n) pq.push({d + 1, i + 1}); // } FOR(i, 0, n - 1) FOR(j, 0, n - 1) dis[j][0] = min(dis[j][0], dis[i][0] + abs(i - j)); FOR(i, 0, n - 2) dis[i][1] = min(dis[i][1], dis[i + 1][0] + 1); ll ans = engiin(sx, sy, tx, ty); FOR(i, 0, n - 1) { ans = min(ans, dis[i][0] + engiin(i, 0, tx, ty)); ans = min(ans, dis[i][1] + engiin(i, a[i], tx, ty)); } cout << ans << "\n"; return 6/22; }
#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...