Submission #1386376

---

Source Code Expand

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int nMax=100010;
int n,t,e,x[nMax];
long long time[nMax];
int main()
{
	scanf("%d%d%d",&n,&e,&t);
	for(int i=1;i<=n;i++)
		scanf("%d",&x[i]);
	sort(x+1,x+1+n);
	int last=1;
	long long ans=time[1]=x[1];
	for(int i=1;i<n;i++)
	{
		if(ans+2*(x[i+1]-x[i])+x[i]-x[last]<=time[last]+t)
			time[i+1]=ans=ans+x[i+1]-x[i];
		else
		{
			long long v1=max((time[last]+t)-(ans+x[i]-x[last]),(long long)0);
			v1+=(long long)2*(x[i]-x[last])+x[i+1]-x[i]+t;
			long long v2=(long long)3*(x[i+1]-x[i])+(long long)2*(x[i]-x[last]);
			if(v1<=v2)
			{
				time[i+1]=ans=ans+v1-t;
				last=i+1;
			} else
				time[i+1]=ans=ans+x[i+1]-x[i];
		}
	}
	ans+=max((time[last]+t)-(ans+x[n]-x[last]),(long long)0)+(long long)2*(x[n]-x[last])+e-x[n];
	printf("%lld\n",ans);
	return 0;
}

Submission Info

Judge Result