Submission #2067160

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cctype>
#include <complex>
#include <functional>
using namespace std;

#define INF_LL (ll)1e18
#define INF (int)1e9
#define REP(i, n) for(int i = 0;i < (n);i++)
#define FOR(i, a, b) for(int i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using ll = long long;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
using PIII = pair<int, PII>;
const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}


int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll N, L;
	double x[114514] = {};
	double dp[114514] = {};
	fill(dp, dp+114514, INF);
	cin >> N >> L;
	REP(i, N){
		cin >> x[i+1];
	}
	x[N+1] = 2*INF;

	dp[0] = -L;
	REP(i, N){
		if(x[i+1]-dp[i] <= L) continue;
		int in = upper_bound(x, x+N+1, L+x[i+1])-x;
		in--;
		if(x[in]-x[i+1] >= L) continue;
		chmin(dp[in], max(dp[i]+2*L, x[in]+0.1));
		if(i == in)
			chmin(dp[i+1], x[i+1]+0.1);
	}
	if(dp[N] != INF)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}

Submission Info

Judge Result