Submission #1363758

#TimeUsernameProblemLanguageResultExecution timeMemory
1363758AvianshText editor (CEOI24_editor)C++20
0 / 100
383 ms39952 KiB
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int inf = 2e18;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    int sl,sc;
    cin >> sl >> sc;
    sl--;
    sc--;
    int el,ec;
    cin >> el >> ec;
    el--;
    ec--;
    int arr[n];
    for(int &i : arr){
        cin >> i;
        ++i;
    }
    set<array<int,2>>pts[n];
    priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>>pq;
    pq.push({0,sl,sc});
    int dist[n][5005];
    for(int i = 0;i<n;i++){
        fill(dist[i],dist[i]+5005,inf);
    }
    dist[sl][sc]=0;
    while(!pq.empty()){
        array<int,3>a = pq.top();
        pq.pop();
        if(a[1]<0||a[1]>=n){
            continue;
        }
        if(a[2]>=arr[a[1]]){
            a[2]=arr[a[1]]-1;
        }
        if(dist[a[1]][a[2]]<a[0]){
            //better found
            continue;
        }
        //check
        if(a[1]<n-1){
            int x = a[1]+1;
            int y = a[2];
            y=min(y,arr[a[1]]-1);
            if(dist[x][y]>a[0]+1){
                dist[x][y]=a[0]+1;
                pq.push({dist[x][y],x,y});
            }
        }
        if(a[1]){
            int x = a[1]-1;
            int y = a[2];
            y=min(y,arr[a[1]]-1);
            if(dist[x][y]>a[0]+1){
                dist[x][y]=a[0]+1;
                pq.push({dist[x][y],x,y});
            }
        }
        if(a[2]==0){
            if(a[1]){
                int x = a[1]-1;
                int y = arr[a[1]-1]-1;
                if(dist[x][y]>a[0]+1){
                    dist[x][y]=a[0]+1;
                    pq.push({dist[x][y],x,y});
                }
            }
        }
        if(a[2]==arr[a[1]]-1){
            if(a[1]<n-1){
                int x = a[1]+1;
                int y = 0;
                if(dist[x][y]>a[0]+1){
                    dist[x][y]=a[0]+1;
                    pq.push({dist[x][y],x,y});
                }
            }
        }
        if(a[2]!=0&&dist[a[1]][a[2]-1]>a[0]+1){
            dist[a[1]][a[2]-1]=a[0]+1;
            pq.push({dist[a[1]][a[2]-1],a[1],a[2]-1});
        }
        if(a[2]!=arr[a[1]]-1&&dist[a[1]][a[2]+1]>a[0]+1){
            dist[a[1]][a[2]+1]=a[0]+1;
            pq.push({dist[a[1]][a[2]+1],a[1],a[2]+1});
        }
    }
    cout << dist[el][ec];
    return 0;
}

#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...