Submission #1864953

---

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
#define INF 1e18

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef vector < pair<int, int> > vii;
typedef long double ld;
typedef tree<pair<int,int>, null_type, less<pair<int,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 dp[111111], x[111111];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n, e, T;
	cin >> n >> e >> T;
	for(int i = 1; i <= n; i++){
		cin >> x[i];
	}
	dp[1]=x[1]+T;
	for(int i = 2; i <= n; i++){
		dp[i]=INF;
		for(int j = 1; j <= i; j++){
			if(2*(x[i]-x[j])>=T){
				dp[i]=min(dp[i],x[j]-x[j-1]+3*(x[i]-x[j])+dp[j-1]);
			}
			else{
				dp[i]=min(dp[i],x[j]-x[j-1]+3*(x[i]-x[j])+dp[j-1]+T-2*(x[i]-x[j]));
			}
		}
	}cout << dp[n]+e-x[n];
	return 0;
}

Submission Info

Judge Result