Submission #1864827

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

ll x[111111];
ll dp[111111];
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	ll lmin=ll(1e18); 
	deque<pair<ll,ll> > rmin;
	int n; cin>>n; ll e,t; cin>>e>>t;
	if(n>3000){return 0;}
	x[0]=0;
	for(int i=1;i<=n;i++)
	{
		cin>>x[i];
	}
	int ptr=1;
	rmin.pb(mp(dp[0]-x[0]+t,1));
	for(int i=1;i<=n;i++)
	{
		while(ptr<=i&&x[i]>=t/2+x[ptr]+1) //this means that we need to remove ptr from the "T - 2(x_i - x_{j+1})" is large part
		{
			if(!rmin.empty()&&rmin.front().se==ptr) rmin.pop_front();
			lmin = min(lmin, dp[ptr-1]-2*x[ptr]-x[ptr-1]);
			ptr++;
		}
		ll best=lmin;
		if(!rmin.empty()) best=min(best,-2*x[i]+rmin.front().fi);
		dp[i]=best+3LL*x[i];
		ll cost = dp[i]-x[i]+t;
		while(!rmin.empty()&&rmin.back().fi>=cost) rmin.pop_back();
		rmin.pb(mp(cost,i+1));
	}
	cout<<dp[n]+e-x[n];
}

Submission Info

Judge Result