Dのいい感じのやつ.cpp

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

typedef long long int ll;

bool
satisfy(const vector<ll> &xs, ll time)
{
  ll r = 0;

  for (size_t i = 0; i < xs.size() - 1; i++) {
    ll xa = xs[i] - r;
    ll xb = xs[i+1];

    if (xa > time) return false;

    r = min(xb, max(time - xa * 2, (time - xa) / 2));
  }

  return xs[xs.size() - 1] == r;
}

int
main ()
{
  ll n, m;
  vector<ll> xs;

  cin >> n >> m;
  ll x0 = 0, x1;

  for(ll i = 0; i < m; i++) {
    cin >> x1;
    xs.push_back(x1 - x0 - 1);
    x0 = x1;
  }
  xs.push_back(n - x0);

  ll l = -1, r = 3 * n;

  while (l + 1 < r) {
    ll m = (l + r) / 2;
    if (satisfy(xs, m)) r = m; else l = m;
  }

  cout << r << endl;

  return 0;
}