Submission #1779193

---

Source Code Expand

# include <bits/stdc++.h>

using namespace std;

# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define REPD(i, a, b) for(int i = a; i >= b; -- i)
# define REPG(i, h, x) for(int i = h[x]; ~i; i = edge[i].next)

const int N = 1e5 + 5;
typedef long long LL;

int q[N], he, ta;
int n, t, e, var;
LL d[N], f[N];

# define gc getchar
inline int rd() {
	char ch = gc();int ret = 0;
	while(ch < '0' || ch > '9') ch = gc();
	while(ch >= '0' && ch <= '9') ret = ret * 10 + ch - '0', ch = gc();
	return ret;
}

void solve() {
	CLR(f, -1);
	int lm = 0;
	f[0] = 0;
	var = -1;
	he = 1;
	q[++ ta] = 0;
	REP(i, 1, n) {
		while(he <= ta && (d[i] - d[q[he] + 1]) * 2 >= t) ++ he;
		for(lm; lm < q[he]; ++ lm) if(var == -1 || (f[lm] - 2 * d[lm + 1] < f[var] - 2 * d[var + 1])) var = lm;
		if(~var) f[i] = f[var] + 2 * (d[i] - d[var + 1]);//, printf("1[%d %d+%d], ", var, f[var], 2 * (d[i] - d[var + 1])); 
		if(he <= ta) { 
			if(~f[i]) f[i] = min(f[i], f[q[he]] + t);
			else f[i] = f[q[he]] + t;
//			printf("2[%d %d],", q[he], f[q[he]]);
		}
		while(he <= ta && f[q[ta]] > f[i]) -- ta;
		q[++ ta] = i; 
//		printf("%lld\n", f[i]);
	}
	printf("%lld\n", e + f[n]);
}

int main() {
	n = rd(), e = rd(), t = rd();
	REP(i, 1, n) d[i] = rd();
	solve();
	return 0;
}

Submission Info

Judge Result