Submission #1690677

---

Source Code Expand

#include <bits/stdc++.h>

#define int long long

using namespace std;
const int inf = 1e18;
int x[111111], dp[111111], st[444444] = {inf};
void upd(int l, int r, int cur, int ind, int val)
{
    if(ind < l or r < ind or r < l)
        return ;
    if(l == r)
    {
        st[cur] = val;
        return;
    }
    int mid = (l+r)/2;
    upd(mid+1, r, cur*2+2, ind, val);
    upd(l, mid, cur*2+1, ind, val);
    st[cur] = min(st[cur*2+1], st[cur*2+2]);
}
int mn(int l, int r, int sl, int sr, int cur)
{
    if(sr < l or r < sl or r < l or sr < sl)
        return inf;
    if(l == r)
        return st[cur];
    if(sl <= l and r <= sr)
        return st[cur];
    int mid = (l+r)/2;
    return min(mn(l, mid, sl, sr, cur*2+1), mn(mid+1, r, sl, sr, cur*2+2));
}
int32_t main()
{
    int n, t, e;
    cin >> n >> e >> t;
    for(int i = 1; i <= n; i++)
        cin >> x[i];
    upd(0, n, 0, 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(j <= 1)
        {
            dp[j] = t;
        }
        else
        {
            if((x[i]-x[j])*2 < t)
                j--;
            dp[i] = min(dp[j]+t, mn(0,n,0,j-1,0)+2*x[i]);
        }
        upd(0, n, 0, i, dp[i]-2*x[i+1]);
    }
    cout << dp[n]+e << endl;
    return 0;
}

Submission Info

Judge Result