Submission #2843600

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
 
#define pb  push_back
#define mp  make_pair
#define int long long
#define itr ::iterator 
 
typedef pair<int,int>  pii;
 
const int MAX=1e6;
const int INF=1e18;
 
int N,E,T,arr[MAX],dp[MAX],tot[MAX],pre[MAX],nxt[MAX];
 
/*int cal(int ind)
{
	if(ind==N+1)
		return 0;
	if(dp[ind]!=-1)
		return dp[ind];
	dp[ind]=INF;
	for(int A=ind;A<=N;A++)
	{
		if(ok[ind][A] and ok[ind][A+1])
			continue;
		dp[ind]=min(dp[ind],pre[ind][A]+(arr[A+1]-arr[A])+cal(A+1));
	}
	return dp[ind];
}*/
 
void solve()
{
	dp[N]=T+E-arr[N];
	//tot[N]=3*arr[N]+T-arr[N];
	//cout<<dp[N]<<" ha ha \n";
	for(int A=N-1;A>=1;A--)
	{
		dp[A]=pre[A]+arr[nxt[A]+1]-arr[nxt[A]]+dp[nxt[A]+1];
	//	if(nxt[A]<N)
	//		dp[A]=min(dp[A],-3*arr[A]+tot[nxt[A]+1]);
	//	tot[A]=min(tot[A+1],3*arr[A]+arr[A+1]-arr[A]+dp[A+1]);
		for(int B=nxt[A]+1;B<=N;B++)
		{
		//	cout<<dp[A]<<"lol \n";
			dp[A]=min(dp[A],3*(arr[B]-arr[A])+arr[B+1]-arr[B]+dp[B+1]);
			//cout<<dp[A]<<" "<<3*(arr[B]-arr[A])<<" "<<arr[B+1]-arr[B]<<" "<<dp[B+1]<<"lol \n";
		}
		//cout<<A<<" "<<dp[A]<<" "<<pre[A]<<" "<<dp[nxt[A]+1]<<"\n";
	}
	return ;
}
 
signed main()
{
	ios_base::sync_with_stdio(false);
 
	cin>>N>>E>>T;
	for(int A=1;A<=N;A++)
		cin>>arr[A];
	arr[N+1]=E;
	for(int A=1;A<=N;A++)
	{
		int low=A,high=N,mid,res=A;
		while(low<=high)
		{
			mid=(low+high)/2;
			if(T-2*(arr[mid]-arr[A])>0)
			{
				res=mid;
				low=mid+1;
			}
			else
				high=mid-1;
		}
	//	cout<<A<<" "<<res<<"\n";
		nxt[A]=res;
		pre[A]=T-2*(arr[res]-arr[A])+3*(arr[res]-arr[A]);
	}
	solve();
	cout<<arr[1]+dp[1];
	return 0;
}

Submission Info

Judge Result