Submission #1690178

---

Source Code Expand

#include <iostream>

using namespace std;

#define ll long long int

const int mx = 1e5+1 , inf = 1e9;

ll n,e,t;
ll x[mx];
ll dp[mx];
ll mn=inf;

ll ptr=-1;

int main()
{
    cin >> n >> e >> t;
    e*=2;
    t*=2;
    for(int i=0;i<n;i++)
    {
        cin >> x[i];
        x[i]*=2;
    }

    for(int i=0;i<n;i++)
    {
        while(x[ptr+1]<x[i]-t/2)
        {
            ptr++;
            if(ptr>0)
                mn=min(mn, dp[ptr-1]-2*x[ptr]);
            else
                mn=min(mn, 0-2*x[ptr]);
        }
        if(mn==inf)
        {
            dp[i]=t;
            continue;
        }
        dp[i]=mn+2*x[i];

        if(ptr>=0)
            dp[i]=min(dp[i],dp[ptr]+t);
    }

    cout << (dp[n-1] + e)/2;

    return 0;
}

Submission Info

Judge Result