Submission #1101079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101079		Mighilon	Text editor (CEOI24_editor)	C++17	16 / 100	306 ms	18796 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define F0R(i,a) for(int i=0;i<(a);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORd(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define F0Rd(i,a) for(int i=(a)-1;i>=0;--i)
typedef vector<int> vi;

void solve(){
    int n;
    cin>>n;
    int si,sj,ei,ej;
    cin>>si>>sj>>ei>>ej;
    si--,sj--,ei--,ej--;
    vi a(n);
    F0R(i,n)cin>>a[i];
    int res=2e9;
    {
        int aux=0,mn=sj;
        FOR(i,min(si,ei),max(si,ei)+1){
            mn=min(mn,a[i]);
        }
        res=min(res,abs(si-ei)+abs(mn-ej));
    }
    vi mn(n, 1e9);
    int tmp=sj;
    FOR(i,si,n){
        if(i>si)
            mn[i]=min({mn[i],mn[i-1]+1,i-si+a[i-1]-tmp});
        tmp=min(tmp,a[i]);
        mn[i]=min(mn[i],i-si+tmp);
    }
    tmp=sj;
    FORd(i,0,si){
        tmp=min(tmp,a[i]);
        if(i+1<n){
            mn[i+1]=min(mn[i+1],a[i]-tmp+si-i);
            mn[i]=min(mn[i],mn[i+1]+1);
        }
    }
    //F0R(i,n)cout<<mn[i]<<" ";
    //cout<<endl;

    tmp=1e9;
    F0R(i,n){
        mn[i]=min(mn[i],tmp);
        tmp=min(tmp,mn[i]);
        tmp++;
    }
    tmp=1e9;
    F0Rd(i,n){
        mn[i]=min(mn[i],tmp);
        tmp=min(tmp,mn[i]);
        tmp++;
    }
    //F0R(i,n)cout<<mn[i]<<" ";cout<<endl;
    res=min(res,mn[ei]+ej);
    tmp=1e9;
    FOR(i,ei,n-1){
        tmp=min(tmp,a[i]);
        res=min(res,mn[i+1]+abs(ej-tmp)+i-ei+1);
        //cout<<i<<" "<<mn[i+1]<<" "<<ej-tmp<<" "<<i-ei<<" "<<endl;
    }
    //cout<<res<<endl;
    tmp=a[ei];
    FORd(i,1,ei+1){
        tmp=min(tmp,a[i-1]);
        res=min(res,mn[i]+abs(ej-tmp)+ei-i+2);
    }
    cout<<res<<endl;
}

int main() {
    int t=1;
    //cin>>t;
    while(t--)
    solve();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:20:13: warning: unused variable 'aux' [-Wunused-variable]
   20 |         int aux=0,mn=sj;
      |             ^~~

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