Submission #1690217

---

Source Code Expand

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define sec second
using namespace std;


const int MAXN=1e5+100;
const ll INF=1e18;
ll x[MAXN],dp[MAXN],dp2[MAXN];
int main() {
   // cout << "HI" <<endl;
    ll n,E,T;
    cin>>n>>E>>T;
    x[0]=0;
    for(int i=1;i<=n;i++){
        cin>>x[i];
        x[i]*=2;
        dp[i]=INF;
    }
    E*=2;
    dp[0]=0;
    dp2[0]=-x[1]*2;
    for(int i=1;i<=n;i++){
        int j=upper_bound(x+1,x+n+1,(x[i]-T))-x;
        j-=2;
        dp[i]=dp[i-1]+T*2;

        if(j>=0){
            dp[i]=min(dp[i],dp2[j]+x[i]*2);
        }


        dp2[i]=min(dp2[i-1],dp[i]-x[i+1]*2);
      //  cout<<i<<' '<<dp[i]<<' '<<dp2[i]<<' '<<j<<endl;

    }

    cout<<(dp[n]+E)/2<<endl;
    return 0;
}

Submission Info

Judge Result