Submission #1690324

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 2010;
const ll INF = 1LL<<50;

inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	for(; !isdigit(ch); ch = getchar()) if(ch=='-') f=-1;
	for(; isdigit(ch); ch = getchar()) x = (x*10)+(ch^48);
	return x * f;
}

int n, e, T, d[MAXN];
ll dp[MAXN];

int main() {
	n = read();
	e = read(), T = read();
	for(int i = 1; i <= n; i++) d[i] = read();
	dp[0] = 0;
	for(int i = 1; i <= n; i++) {
		dp[i] = INF;
		int f = 0;
		for(int j = 0; j < i; j++) {
			ll res = dp[j]+d[i]-d[j]+max(T, 2*(d[i]-d[j+1]));
			if(res < dp[i]) {
				dp[i] = res;
				f = j;
			}
		}
		//printf("%d\n", f);
	}
	//printf("%lld\n", dp[2]);
	printf("%lld\n", dp[n]+e-d[n]);
	return 0;
}

Submission Info

Judge Result