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;
typedef long long ll;
ll s[202020];
priority_queue <ll> L;
priority_queue <ll, vector <ll>, greater <ll> > R;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int n; ll h;
cin >> n >> h;
for(int i = 1; i <= n; i++) {
cin >> s[i];
}
ll ans = 0;
L.push(s[1]), R.push(s[1]);
for(int i = 2; i <= n; i++) {
ll l = L.top() - h * (i - 1), r = R.top() + h * (i - 1);
if(s[i] < l) {
ans += l - s[i];
L.push(s[i] + h * (i - 1));
L.push(s[i] + h * (i - 1));
R.push(l - h * (i - 1));
L.pop();
}
else if(s[i] > r) {
ans += s[i] - r;
R.push(s[i] - h * (i - 1));
R.push(s[i] - h * (i - 1));
L.push(r + h * (i - 1));
R.pop();
}
else {
l = r = s[i];
L.push(s[i] + h * (i - 1));
R.push(s[i] - h * (i - 1));
}
}
cout << ans;
}
# | 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... |