Submission #1612140

---

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=100010;
	const ll INF=214748364700000ll;
	struct Increasing_queue
	{
		ll dl[N];
		int pos[N];
		int head,tail;
		void init(){head=0,tail=1;}
		void insert(ll x,int p)
		{
			while(head>=tail && dl[head]>=x)head--;
			dl[++head]=x;
			pos[head]=p;
		}
		void del(int p)
		{
			while(head>=tail && pos[tail]<=p)tail++;
		}
		ll query(){return head>=tail?dl[tail]:INF;}
	}d;
	int a[N],b[N];
	ll f[N],tmp;
	int n,m;
	void initialize()
	{
		read(n),read(a[n]),read(m);
		for(int i=0;i<n;i++)
			read(a[i]);
		for(int i=1;i<=n;i++)
			b[i]=a[i]-a[i-1];
	}
	inline ll get_dis(int i,int j){return a[j]-b[j]-a[i];}
//	inline ll calc(int i,int j)
//	{
//		ll dis=get_dis(i,j),ret=dis*3+b[j];
//		ret+=std::max(0ll,m-dis*2);
//		return ret;
//	}
	void solve()
	{
		initialize();

		d.init(),tmp=INF;
		f[0]=a[0],d.insert(f[0]-a[0],0);
		int ind=0;

		for(int i=1;i<=n;i++)
		{
			for(;ind<i && get_dis(ind,i)*2>m;ind++)
				d.del(ind),check_min(f[ind]-3*a[ind],tmp);

			f[i]=d.query()+a[i]+m;
			check_min(tmp+3*a[i]-2*b[i],f[i]);

			d.insert(f[i]-a[i],i);
		}
		printf("%lld\n",f[n]);
	}
}
int main()
{
	bf::solve();
	return 0;
}

Submission Info

Judge Result