This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int a[200100];
void solve(){
int n, h;
cin>>n>>h;
for(int i=1; i<=n; i++){
cin>>a[i];
}
multiset<ll> ql, qr;
ql.insert(a[1]);
qr.insert(a[1]);
ll ans = 0;
for(int i=2; i<=n; i++){
ll add = h * (i - 1);
ll l=*ql.rbegin()-add, r=*qr.begin()+add;
ll t = a[i];
if(l <= t and t <= r){
ql.insert(t+add);
qr.insert(t-add);
}
else if(l > t){
ans += l-t;
qr.insert(l-add);
ql.erase(ql.find(l + add));
ql.insert(t+add);
ql.insert(t+add);
}
else if(r < t){
ans += t - r;
ql.insert(r+add);
qr.erase(qr.find(r - add));
qr.insert(t-add);
qr.insert(t-add);
}
}
cout<<ans<<'\n';
}
int main(){
solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |