Submission #1231225

#TimeUsernameProblemLanguageResultExecution timeMemory
1231225alexander707070Text editor (CEOI24_editor)C++20
45 / 100
15 ms4372 KiB
#include<bits/stdc++.h>
#define MAXN 1007
using namespace std;

const long long inf=1e15;

int n;
int srow,scol,erow,ecol;
int h[MAXN];
int minh[MAXN][MAXN];
long long ans;

long long go_straight(int r1,int c1,int r2,int c2){
    if(r1<1 or r1>n)return inf;
    if(r2<1 or r2>n)return inf;

    return abs(r1-r2) + abs( min(c1,minh[min(r1,r2)][max(r1,r2)]) - c2);
}

int main(){

    cin>>n;

    cin>>srow>>scol;
    cin>>erow>>ecol;

    for(int i=1;i<=n;i++){
        cin>>h[i];
        h[i]++;
    }

    for(int i=1;i<=n;i++){
        minh[i][i]=h[i];

        for(int f=i+1;f<=n;f++){
            minh[i][f]=min(h[f],minh[i][f-1]);
        }
    }

    ans=go_straight(srow,scol,erow,ecol);

    for(int i=1;i<=n;i++){
        if(i>1)ans=min(ans , go_straight(srow,scol,i,1) + 1 + go_straight(i-1,h[i-1],erow,ecol) );
        if(i<n)ans=min(ans , go_straight(srow,scol,i,h[i]) + 1 + go_straight(i+1,1,erow,ecol) );

        ans=min(ans , go_straight(srow,scol,i,h[i]) + go_straight(i,h[i],erow,ecol) );
    }

    for(int i=1;i<=n;i++){
        for(int f=1;f<=n;f++){
            ans=min(ans , go_straight(srow,scol,i,h[i]) + 1 + go_straight(i+1,1,f,1) + 1 + go_straight(f-1,h[f-1],erow,ecol) );

            ans=min(ans , go_straight(srow,scol,i,h[i]) + go_straight(i,h[i],f,1) + 1 + go_straight(f-1,h[f-1],erow,ecol) );
        }
    }

    cout<<ans<<"\n";
    
    return 0;
}
#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...