Atcoder - いろはちゃんコンテスト Day1 - E - 放課後

問題概要

E - 放課後

解法

0 →Di → Di+1...Di+B→Nの間でどれだけAの区間が得られるか数えればよい。
数えた結果、Dに到達していれば0、Dに到達していなければ
必要なAの区間の個数が解となる。

提出コード

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define INF 1e9
vector<ll> a;

int main()
{
	ll n, x, y;
	cin >> n >> x >> y;
	if (y == 0) {
		cout << 0 << endl;
		exit(0);
	}
	for(ll i = 0; i < y; i++) {
		ll k;
		cin >> k;
		a.push_back(k);
	}
	a.push_back(0);
	sort(a.begin(), a.end());
	ll count = y;
	for (ll i = 0; i < y; i++) {
		ll k = a[i + 1] - a[i] - x;
		count += std::max((ll)(std::ceil((double)k / x)), (ll)0);
	}
	ll k = n - a.back();
	count += std::max((ll)(std::ceil(k/x)), (ll)0);
	ll ans = n - count;
	cout << ans << endl;
	return 0;
}