제출 #1134357

#제출 시각아이디문제언어결과실행 시간메모리
1134357AiperiiiText editor (CEOI24_editor)C++20
14 / 100
121 ms43740 KiB
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
using namespace std;

vector <int> dis[1005];
signed main(){
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    int n;
    cin>>n;
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    
    
    
    
    
    
    vector <int> l(n);
    
    for(int i=0;i<n;i++){
        cin>>l[i];
        if(n>=3){
            dis[i+1].pb(-1);
            for(int j=0;j<l[i]+1;j++){
                dis[i+1].pb(-1);
            }
        }
        
       
    }
    if(n==1){
        cout<<abs(b-d)<<"\n";
        return 0;
    }
    
    if(n==2){
        if(a==c){
            cout<<abs(b-d)<<"\n";
        }
        else{
            if(b==d)cout<<1<<"\n";
            else if(b>d){
                
                    cout<<min(b-d+1,max(min(l[0]+1,l[1]+1),b)-b +1 +min(l[0]+1,l[1]+1)-d)<<"\n";
                
            }
            else {
                cout<<min(d-b+1,max(min(l[0]+1,l[1]+1),b)-b +1 +min(l[0]+1,l[1]+1)-d)<<"\n";
            }
        }
        return 0;
    }
    
    dis[a][b]=0;
    // aaaa bbb
    queue <pair <int,int> >  q;
    q.push({a,b});
    
    while(!q.empty()){
        int x=q.front().ff;
        int y=q.front().ss;
        q.pop();
        if(y-1>=1){
            if(dis[x][y-1]==-1){
                dis[x][y-1]=dis[x][y]+1;
                q.push({x,y-1});
            }
        }
        else if(x-1>=1){
            if(dis[x-1][l[x-2]+1]==-1){
                dis[x-1][l[x-2]+1]=dis[x][y]+1;
                q.push({x-1,l[x-2]+1});
            }
        }
        
        if(y+1<=l[x-1]+1){
            if(dis[x][y+1]==-1){
                dis[x][y+1]=dis[x][y]+1;
                q.push({x,y+1});
            }
        }
        else if(x+1<=n){
            if(dis[x+1][1]==-1){
                dis[x+1][1]=dis[x][y]+1;
                q.push({x+1,1});
            }
        }
        
        
        if(x-1>=1){
            if(dis[x-1][min(y,l[x-2]+1)]==-1){
                dis[x-1][min(y,l[x-2]+1)]=dis[x][y]+1;
                q.push({x-1,min(y,l[x-2]+1)});
            }
        }
        
        if(x+1<=n){
            if(dis[x+1][min(y,l[x]+1)]==-1){
                dis[x+1][min(y,l[x]+1)]=dis[x][y]+1;
                q.push({x+1,min(y,l[x]+1)});
            }
        }
    }
    cout<<dis[c][d]<<"\n";
}
/*

*/


#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...