#include <bits/stdc++.h>
#define ll long long
#define lb lower_bound
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F first
#define S second
#define ld long double
#define pb push_back
#define all(v) v.begin(),v.end()
#define in insert
#define sz(s) (int)s.size()
#define int ll
using namespace std;
const int MAX=2e5+10;
const int inf=2e9;
int n,H;
int a[MAX];
void solve(){
cin>>n>>H;
multiset<int> l,r;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int st=0;
int slope=0;
int add=0;
for(int i=1;i<=n;i++){
add+=H;
st+=a[i]+add;
slope--;
l.in(a[i]+add);
l.in(a[i]+add);
while(!r.empty()&&!l.empty()&&*l.rbegin()-2*add>*r.begin()){
int L=*r.begin()+2*add;
int R=*l.rbegin()-2*add;
l.erase(--l.end());
r.erase(r.begin());
l.in(L);
r.in(R);
}
while(sz(l)>abs(slope)){
r.in(*l.rbegin()-2*add);
l.erase(--l.end());
}
}
vector<int> vec;
for(int x:l){
// cout<<x-add<<" ";
vec.pb(x-add);
}
// cout<<"\n";
// cout<<st<<" "<<*r.rbeg<<"\n";
int prev=-add;
for(int i=0;i<sz(vec);i++){
st+=(vec[i]-prev)*slope;
prev=vec[i];
slope++;
}
cout<<st<<"\n";
}
// #ifdef LOCAL
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
}
// #endif
Compilation message
cc1plus: error: '::main' must return 'int'
