제출 #1150392

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

Main

#include <bits/stdc++.h>
#define ff first
#define ss second
#define int long long
using namespace std;
const int MAXN = 1e5+5;
int N, sx, sy, tx, ty;
int len[MAXN],dist[MAXN],A[MAXN],B[MAXN],C[MAXN];
bool vis[MAXN<<2];
map<pair<int,int>,int> mp;
int nodescnt;
vector<pair<int,int>> adj[MAXN];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
void add(int u, int v, int w){
    adj[u].push_back({v,w});
}
void dijkstra(){
    while(!pq.empty()){
        int u = pq.top().ss, cd = pq.top().ff; pq.pop();
        if(vis[u]) continue;
        vis[u] = true;
        for(auto pa : adj[u]){
            int v = pa.ff;
            if(dist[v] > dist[u]+pa.ss){
                dist[v] = dist[u]+pa.ss;
                pq.push({dist[v],v});
            }
        }
    }
}
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N;
    cin >> sx >> sy >> tx >> ty;
    for(int i = 1;i<=N;++i) cin >> len[i];
    for(int i = 1;i<=N;++i){
        mp[{i,1}] = ++nodescnt;
        mp[{i,len[i]+1}] = ++nodescnt;
        if(sy < len[i]+1) mp[{i,sy}] = ++nodescnt;
        A[i] = mp[{i,1}], B[i] = mp[{i,sy}], C[i] = mp[{i,len[i]+1}];
        if(B[i]){
            add(A[i],B[i],sy-1);
            add(B[i],A[i],sy-1);
            add(B[i],C[i],len[i]+1-sy);
            add(C[i],B[i],len[i]+1-sy);
        }
        else{
            add(A[i],C[i],len[i]);
            add(C[i],A[i],len[i]);
        }
    }
    for(int i = 1;i<=nodescnt;++i) dist[i] = 2147483647;
    for(int i = sx, tmp = sy;i;i--){
        tmp = min(tmp,len[i]+1);
        int id = mp[{i,tmp}];
        dist[id] = sx-i;
        pq.push({dist[id],id});
    }
    for(int i = sx, tmp = sy;i<=N;++i){
        tmp = min(tmp,len[i]+1);
        int id = mp[{i,tmp}];
        dist[id] = i-sx;
        pq.push({dist[id],id});
    }
    for(int i = 1;i<N;++i){
        add(A[i],A[i+1],1); add(A[i+1],A[i],1);
        add(A[i],C[i+1],len[i+1]+1); add(C[i+1],A[i],len[i+1]+1);
        add(C[i],A[i+1],1); add(A[i+1],C[i],1);
        if(len[i] >= len[i+1]){
            add(C[i],C[i+1],1);
            add(C[i+1],C[i],len[i]-len[i+1]+1);
        }
        if(len[i] <= len[i+1]){
            add(C[i+1],C[i],1);
            add(C[i],C[i+1],len[i+1]-len[i]+1);
        }
        if(B[i] && B[i+1]){
            add(B[i],B[i+1],1);
            add(B[i+1],B[i],1);
        }
        if(B[i]){
            add(B[i],C[i+1],B[i+1] ? (len[i+1]+1-sy+1) : 1);
            add(B[i],A[i+1],sy);
            add(C[i+1],B[i],abs(sy-len[i+1]));
            add(A[i+1],B[i],sy);
        }
        if(B[i+1]){
            add(A[i],B[i+1],sy);
            add(C[i],B[i+1],abs(sy-len[i]));
            add(B[i+1],C[i],B[i] ? (len[i]+1-sy+1) : 1);
            add(B[i+1],A[i],sy);
        }
    }
    dijkstra();
    int ans = 2147483647;
    int tmp = len[tx]+1;
    for(int i = tx;i;--i){
        tmp = min(tmp,len[i]+1);
        ans = min(ans,dist[A[i]]+tx+ty-i-1);
        ans = min(ans,dist[C[i]]+tx-i+abs(len[i]+1-tmp)+abs(ty-tmp));
        if(B[i]) ans = min(ans,dist[B[i]]+tx-i+abs(ty-sy)+abs(tmp-sy));
    }
    tmp = len[tx]+1;
    for(int i = tx;i <= N;++i){
        tmp = min(tmp,len[i]+1);
        ans = min(ans,dist[A[i]]+i-tx+ty-1);
        ans = min(ans,dist[C[i]]+i-tx+abs(len[i]+1-tmp)+abs(ty-tmp));
        if(B[i]) ans = min(ans,dist[B[i]]+i-tx+abs(ty-tmp)+abs(tmp-sy));
    }
    tmp = 2147483647;
    for(int i = min(sx,tx);i<=max(tx,sx);++i) tmp = min(tmp,len[i]+1);
    if(tmp >= sy && tmp >= ty){
        ans = min(ans,abs(sx-tx)+abs(sy-ty));
    }
    cout << ans << "\n";
    return 0;
}

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