Submission #1436961

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n,e,t;
  cin>>n>>e>>t;
  int x[n+1];
  for(int i=0;i<n;i++) cin>>x[i];
  if(n>2000) assert(0);
  x[n]=e;
  int dp[n+1];
  int INF=1LL<<55LL;
  fill_n(dp,n+1,INF);
  dp[0]=x[0];
  for(int j=0;j<n;j++){
    int res=dp[j+1];
    for(int i=0;i<=j;i++){
      int tmp=max(2*(x[j]-x[i]),t);
      tmp+=x[j+1]-x[i];
      res=min(res,dp[i]+tmp);
    }
    dp[j+1]=res;
  }
  cout<<dp[n]<<endl;
  return 0;
}

Submission Info

Judge Result