#include typedef long long ll; typedef unsigned long long ull; #define FOR(i,a,b) for(int (i)=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define RANGE(vec) (vec).begin(),(vec).end() using namespace std; class UFTree { std::vector par_; std::vector rank_; int size_; public: UFTree(int N) { init(N); } UFTree() {} ~UFTree() {} void init(int N) { par_.resize(N); rank_.resize(N, 0); for (int i = 0; i < N; ++i) par_[i] = i; size_ = N; } int find(int x) { assert(0 <= x && x < par_.size()); if ( par_[x] == x ) return x; else return ( par_[x] = find(par_[x])); } void unite(int x, int y) { assert(0 <= x && x < par_.size()); assert(0 <= y && y < par_.size()); x = find(x); y = find(y); if ( x == y ) return; --size_; if ( rank_[x] < rank_[y] ) par_[x] = y; else { par_[y] = x; if ( rank_[x] == rank_[y] ) ++rank_[x]; } } bool same(int x, int y) { return (find(x) == find(y)); } size_t size() { return size_; } // find 経由で par を更新してからでないと par へのアクセスは危険 int operator[](size_t i) { return find(i); } }; class ManyAmeba { public: void solve(void) { int N,D,T; cin>>N>>D>>T; vector X(N); REP(i,N) cin>>X[i]; sort(RANGE(X)); UFTree uft(N); // O(N^2*A) REP(i,N) FOR(j,i,N) { // 時間 T 以内で同じ座標に到達しうるもの同士をまとめる // 距離の差が D 倍なら T が十分に大きいとき同じ座標に到達する。 // X[i],X[j] 双方から進んでくるとみなせるので距離の差の半分を T 時間内の // 移動できるなら条件を満たす。 if (abs(X[i]-X[j])%D==0 && abs(X[i]-X[j])/D <= 2*T) uft.unite(i,j); } map> group; // まとめたものの最大・最小位置を求める REP(i,N) { // 初期化 if (!group.count(uft[i])) group.emplace(piecewise_construct, forward_as_tuple(uft[i]), forward_as_tuple(X[i],X[i])); auto &rng = group[uft[i]]; rng.first = min(rng.first, X[i]); rng.second = max(rng.second, X[i]); } ll sum = 0; // 計算 for (auto g : group) { ll b,e; tie(b,e) = g.second; // 前後を埋める sum += 2*T; // 中間を埋める sum += ((e-b)/D+1); } cout<solve(); delete obj; return 0; } #endif