Submission #1690263

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 1e18;
int x[111111], dp[111111], pmn[111111];
int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n, t, e;
    cin >> n >> e >> t;
    for(int i = 1; i <= n; i++)
        cin >> x[i];
    pmn[0] = -2*x[1];
    for(int i = 1; i <= n; i++)
    {
        int j = lower_bound(x+1, x+n+1, x[i]-t/2.0)-x;
        if((x[i]-x[j])*2 < t)
            j--;
        dp[i] = min(dp[j]+t, pmn[j-1]+2*x[i]);//mn(0,n,0,j-1,0)+2*x[i]);
        pmn[i] = min(pmn[i-1], dp[i]-2*x[i+1]);
    }
    cout << dp[n]+e << endl;
    return 0;
}

Submission Info

Judge Result