제출 #1137717

#제출 시각아이디문제언어결과실행 시간메모리
1137717SyedSohaib_123Text editor (CEOI24_editor)C++20
19 / 100
83 ms43592 KiB
#include <bits/stdc++.h>

using namespace std;

#define append push_back
#define int long long

const int N=1e3,LG=1e4;
int mod=1e9+7;

int mn[N][LG];

void solve(int tst) {
    int n;
    cin>>n;
    int a,b,x,y;
    cin>>a>>b>>x>>y;
    vector<int>v(n+1,0);
    int mx=0;
    for(int i=1;i<=n;i++){
        cin>>v[i];
        mx=max(mx,v[i]);
        v[i]++;
    }
    if(n<=2){
        if(x==1){
            cout<<min({abs(b-y),y+1-(a==2),v[1]-y+2-(a==2)});
        }
        else if(x==2){
            cout<<(a==1)<<endl;
        }
        return;
    }
    mn[a][b]=1;
    deque<pair<int,int>>d;
    d.append({a,b});
    while(d.size()){
        auto [i,j]=d[0];
        d.pop_front();
        //up
        if(i>1 and !mn[i-1][min(v[i-1],j)]){
            mn[i-1][min(v[i-1],j)]=mn[i][j]+1;
            d.append({i-1,min(v[i-1],j)});
        }
        // down
        if(i<n and !mn[i+1][min(v[i+1],j)]){
            mn[i+1][min(v[i+1],j)]=mn[i][j]+1;
            d.append({i+1,min(v[i+1],j)});
        }
        //->
        if(!(i==n and j==v[n])){
            if(j!=v[i]){
                if(!mn[i][j+1]){
                    mn[i][j+1]=mn[i][j]+1;
                    d.append({i,j+1});
                }
            }
            else{
                if(!mn[i+1][1]){
                    mn[i+1][1]=mn[i][j]+1;
                    d.append({i+1,1});
                }
            }
        }
        //<-
        if(!(i==1 and j==1)){
            if(j!=1){
                if(!mn[i][j-1]){
                    mn[i][j-1]=mn[i][j]+1;
                    d.append({i,j-1});
                }
            }
            else{
                if(!mn[i-1][v[i-1]]){
                    mn[i-1][v[i-1]]=mn[i][j]+1;
                    d.append({i-1,v[i-1]});
                }
            }
        }
    }
    cout<<mn[x][y]-1<<endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int i = 0; i < t; i++) {
        solve(i);
    }
}
#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...