Submission #980054

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int M = 100100;

int n;
ll t, e;
ll x[M], d[M];

void read() {
  cin >> n >> e >> t;
  x[0] = 0;
  for (int i = 1; i <= n; ++i)
    cin >> x[i];
}


void kill() {
  d[0] = 0;
  int l = 0;
  ll mn = 0;
  for (int i = 1; i <= n; ++i) {
    d[i] = d[i - 1] + t;
    for (int j = 0; j < i; ++j)
      d[i] = min(d[i], d[j] + max(t, 2 * (x[i] - x[j + 1])));
    continue;
    while (l < i && 2 * (x[i] - x[l + 1]) >= t) {
      mn = min(mn, d[l] + 2 * (x[i] - x[l + 1]));
      ++l;
    }
    d[i] = min(d[i], mn + 2 * x[i]);
  }

  ll ans = d[n] + e;
  
  cout << ans << endl;
}

int main() {
  cout.precision(20);
  cout << fixed;
  ios_base::sync_with_stdio(false);
  read();
  kill();
}

Submission Info

Judge Result