제출 #1195223

#제출 시각아이디문제언어결과실행 시간메모리
1195223TurkhuuText editor (CEOI24_editor)C++20
0 / 100
1 ms396 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;
ll dis(ll sx, ll sy, ll tx, ll ty) {
    return abs(sx - tx) + abs(sy - ty);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; ll sx, sy, tx, ty;
    cin >> n >> sx >> sy >> tx >> ty;
    sy--, ty--;
    vector<ll> a(n);
    for (auto& x : a) cin >> x;
    auto s = a;
    s.push_back(sy);
    s.push_back(ty);
    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end());
    int m = s.size();
    map<ll, int> id;
    FOR(i, 0, m - 1) id[s[i]] = i;
    vector dis(n, vector<ll>(m, 1e18));
    priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> pq;
    for (pq.push({dis[sx][id[sy]] = 0, sx, id[sy]}); !pq.empty(); pq.pop()) {
        auto [d, x, _y] = pq.top();
        if (d != dis[x][_y]) continue;
        ll y = s[_y];
        vector<array<ll, 3>> moves;
        if (x) {
            moves.push_back({x - 1, id[min(a[x - 1], y)], 1});
            moves.push_back({x - 1, id[a[x - 1]], y + 1});
        }
        if (x + 1 < n) {
            moves.push_back({x + 1, id[min(a[x + 1], y)]});
            moves.push_back({x + 1, 0, a[x] - y + 1});
        }
        for (auto [u, v, w] : moves) if (d + w < dis[u][v]) pq.push({dis[u][v] = d + w, u, v});
    }
    ll ans = 1e18;
    FOR(i, 0, m - 1) ans = min(ans, dis[tx][i] + abs(s[i] - 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...