제출 #1137622

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1137622		Ghulam_Junaid	Text editor (CEOI24_editor)	C++20	45 / 100	4104 ms	278856 KiB

Main

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

const int N = 1e6 + 10; // 3e6
int n, len[N], sl, sc, el, ec;

map<pair<int, int>, int> dist;
set<pair<int, pair<int, int>>> st;

int distance(int x, int y){
    if (dist.find({x, y}) == dist.end())
        dist[{x, y}] = 2e9;
    return dist[{x, y}];
}

void upd(int x, int y, int nd){
    if (distance(x, y) > nd){
        st.erase({dist[{x, y}], {x, y}});
        dist[{x, y}] = nd;
        st.insert({dist[{x, y}], {x, y}});
    }
}

void dijkstra(int x, int y){
    upd(x, y, 0);
    while (!st.empty()){
        auto [d, P] = *st.begin();
        auto [x, y] = P;
        st.erase(st.begin());

        upd(x, 0, d + y);
        upd(x, len[x], d + len[x] - y);
        if (x - 1 > 0){
            int up = min(len[x - 1], y);
            upd(x - 1, up, d + 1);
        }
        if (x + 1 <= n){
            int down = min(len[x + 1], y);
            upd(x + 1, down, d + 1);
        }
        if (y == 0)
            if (x - 1 > 0)
                upd(x - 1, len[x - 1], d + 1);
        if (y == len[x])
            if (x + 1 <= n)
                upd(x + 1, 0, d + 1);
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> sl >> sc >> el >> ec;
    sc--, ec--;
    for (int i = 1; i <= n; i ++)
        cin >> len[i];

    dijkstra(sl, sc);

    int ans = 2e9;
    for (auto [P, d] : dist){
        auto [x, y] = P;
        if (x != el) continue;
        ans = min(ans, d + abs(y - ec));
    }
    cout << ans << endl;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 26 / 26
• Subtask 4: 0 / 11
• Subtask 5: 0 / 44