Submission #1385781

---

Source Code Expand

    #include <bits/stdc++.h>
    using namespace std;
    const int MAX = (1e5)+1;
     
    int n;
    long long E, T, x[MAX], dp[MAX], f[MAX];
    multiset<long long> l, m;
    int main() {
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cin >> n >> E >> T;
    	l.insert(f[0] = T);
    	for(int i = 1, j = 0; i <= n; i++) {
    		cin >> x[i];
    		while(j < i && 2*(x[i]-x[j+1]) >= T) {
    			l.erase(l.find(f[j]));
    			f[j] = f[j]-T-2*(x[j+1]);
    			m.insert(f[j]);
    			j++;
    		}
    		dp[i] = LLONG_MAX;
    		if(!l.empty()) dp[i] = min(x[i]+*l.begin(), dp[i]);
    		if(!m.empty()) dp[i] = min(3*x[i]+*m.begin(), dp[i]);
    		l.insert(f[i] = dp[i]-x[i]+T);
    	}
    	cout << dp[n]+E-x[n];
    }

Submission Info

Judge Result