Submission #1611998

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<cstring>
template<typename T>inline void check_min(T a,T &b){if(a<b)b=a;}
template<typename T>inline void read(T &x)
{
	char c=x=0;
	for(c=getchar();!isdigit(c);c=getchar());
	for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
}
namespace bf
{
	typedef long long ll;
	const int N=2010;
	const ll INF=9223372036854775807ll;
	int pos[N];
	ll f[N];
	int n,m;
	void initialize()
	{
		read(n),read(pos[n+1]),read(m);
		for(int i=1;i<=n;i++)
			read(pos[i]);
	}
	ll calc(int i,int j)
	{
		ll dis=pos[j]-pos[i+1], ret=dis*3+pos[j+1]-pos[j];
		ret+=std::max(0ll,m-dis*2);
		return ret;
	}
	void solve()
	{
		initialize();
		f[0]=pos[1];
		for(int i=1;i<=n;i++)
		{
			f[i]=INF;
			for(int j=0;j<i;j++)
				check_min(f[j]+calc(j,i),f[i]);
		}
		printf("%lld\n",f[n]);
	}
}
int main()
{
	bf::solve();
	return 0;
}

Submission Info

Judge Result