/* #include #include typedef boost::multiprecision::cpp_int mlint; */ #include using namespace std; #define esc(x) cout << (x) << endl,exit(0) #define fcout(d) cout << fixed << setprecision(d) #define each(i,v) for(auto i = begin(v),end_copy = end(v); i != end_copy; ++i) #define reach(i,v) for(auto i = rbegin(v),rend_copy = rend(v); i != rend_copy; ++i) #define urep(i,s,t) for(int i = (int)(s),t_copy = (int)t; i <= t_copy; ++i) #define drep(i,s,t) for(int i = (int)(s),t_copy = (int)t; i >= t_copy; --i) #define rep(i,n) urep(i,0,(n) - 1) #define rep1(i,n) urep(i,1,(n)) #define rrep(i,n) drep(i,(n) - 1,0) #define all(v) begin(v),end(v) #define rall(v) rbegin(v),rend(v) #define vct vector #define prique priority_queue #define l_bnd lower_bound #define u_bnd upper_bound #define rsz resize #define ers erase #define emp emplace #define emf emplace_front #define emb emplace_back #define pof pop_front #define pob pop_back #define mkp make_pair #define mkt make_tuple #define fir first #define sec second typedef long long ll; typedef double db; typedef vct> mat; typedef pair pii; typedef pair pli; typedef pair pdi; typedef map mpii; #ifdef Local #define print(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl clock_t starting_time = clock(); #endif void setup() { cin.tie(0); ios::sync_with_stdio(false); #ifdef Local cout << "-- Execution At Local ---\n" << "\n\n\n"; auto print_info = []() { cout << "\n----------------\n"; cout << "\nExec time : " << (double)(clock() - starting_time) / CLOCKS_PER_SEC * 1000 << " ms\n\n"; }; atexit(print_info); #endif } template ostream& operator << (ostream& s, pair p) { return s << p.fir << " " << p.sec; } template ostream& operator << (ostream& s, vector& v) { for(auto i = v.begin(); i != v.end(); i++) { if(i != begin(v)) s << " "; s << *i; } return s; } template void hash_combine(size_t &seed, T const &key) { hash hasher; seed ^= hasher(key) + 0x9e3779b9 + (seed << 6) + (seed >> 2); } namespace std { template struct hash> { size_t operator()(pair const &p) const { size_t seed(0); hash_combine(seed,p.first); hash_combine(seed,p.second); return seed; } }; } bool odd(ll x) { return x & 1; } bool even(ll x) { return !odd(x); } bool parity(ll x, ll y) { return odd(x) ^ even(y); } bool bit(ll n, uint8_t e) { return n & 1LL << e; } int ilog(ll x, uint64_t b) { int ret = 0; while(x /= b) ret++; return ret; } ll qceil(ll x, ll y) { return x > 0 ? (x - 1) / y + 1 : x / y; } ll gcd(ll a, ll b) { if(!b) return abs(a); if(a % b) return gcd(b, a % b); return b; } ll lcm(ll a, ll b) { if(a & b) return a / gcd(a, b) * b; return 0; } template bool chmax(T& m, U x) { if(m < x) { m = x; return 1; } return 0; } template bool chmin(T& m, U x) { if(m > x) { m = x; return 1; } return 0; } template T cmprs(T& v) { T tmp = v; sort(all(tmp)); tmp.erase(unique(all(tmp)),end(tmp)); each(i,v) *i = l_bnd(all(tmp),*i) - begin(tmp) + 1; return v; } const int dir[8][2] = { {1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,1},{-1,-1},{1,-1} }; const ll inf32 = (1 << 30) - 1; const ll inf64 = (1LL << 62) - 1; const ll mod = 1e9 + 7; const db eps = 1e-15; template struct CHT { struct line { K slop,incp; int time; }; // unordered_map toI; vector toK; vector data; int dom = 1; // the width of the domain [0,dom) int clock = 0; // the number of total addition bool conv = 0; CHT(int n) { while(n >= dom) dom <<= 1; dom = dom * 2 + 1; data.resize(dom << 1); } CHT(const vector &sorted) : toK(sorted) { conv = 1; int n = toK.size(); while(n >= dom) dom <<= 1; dom = dom * 2 + 1; data.resize(dom << 1); dom = n; // for(int i = 0; i < n; ++i) { // toI[S[i]] = i; // } } int conv_toI(K x) { // if(conv) return toI[x]; if(conv) return lower_bound(begin(toK),end(toK),x) - begin(toK); return x + dom / 2; } K conv_toK(int i) { if(conv) return toK[i]; return i - dom / 2; } K getval(const line& ln, K x) { return x * ln.slop + ln.incp; } K query(K x) { return getval(find(conv_toI(x)),x); } bool is_lower(const line& ln, int i) { return query(conv_toK(i)) > getval(ln,conv_toK(i)); } const line& find(int i) { int latest = 0,idx; i += dom; while(i) { if(data[i].time > latest) { latest = data[i].time; idx = i; } i >>= 1; } return data[idx]; } //for the interval [i,j) void update(const line& ln, int i, int j) { i += dom; j += dom; while(i < j) { if(i & 1) data[i++] = ln; if(j & 1) data[--j] = ln; i >>= 1, j >>= 1; } } int intersect(const line& ln, int low, int up) { while(abs(low - up) > 1) { int mid = (up + low) / 2; if(is_lower(ln,mid)) low = mid; else up = mid; } return low; } bool add(K s, K t) { line ln = {s,t,++clock}; if(clock == 1) { fill(begin(data),end(data),ln); return true; } int ok = dom - 1; int ng = -1; while(ok - ng > 1) { int mid = (ok + ng) / 2; if(find(mid).slop > s) ng = mid; else ok = mid; } if(!ok) { if(!is_lower(ln,0)) return false; update(ln,0,intersect(ln,0,dom) + 1); return true; } if(is_lower(ln,ok)) { update(ln,intersect(ln,ok,0),intersect(ln,ok,dom) + 1); return true; } ok--; if(is_lower(ln,ok)) { update(ln,intersect(ln,ok,0),intersect(ln,ok,dom) + 1); return true; } return false; } }; ll N,A,B; ll D[300010]; ll dp[300010]; int main() { setup(); cin >> N >> A >> B >> dp[0]; rep1(i,N) cin >> D[i]; vector s; for(int i = 1; i <= N; i++) s.emb(i); CHT cht(s); for(ll i = 1; i <= N; i++) { cht.add(-B * (i - 1),dp[i - 1] + A * i + i * (i - 1) / 2 * B); dp[i] = D[i] - A * i + i * (i - 1) / 2 * B + cht.query(i); } ll ans = inf64; for(ll i = 0; i <= N; i++) { ans = min(ans,dp[i] + (N - i) * (N + 1 - i) / 2 * B - A * (N - i)); } esc(ans); }