#include <bits/stdc++.h>
using namespace std;
using ll = long long;
/*
Slope Trick data structure (đã tinh gọn từ implementation đình đám)
Dùng 2 heap để lưu các điểm đổi độ dốc (slope-changing points)
and track min cost trên toàn hàm f(x).
*/
struct SlopeTrick {
priority_queue<ll> L; // max-heap
priority_queue<ll, vector<ll>, greater<ll>> R; // min-heap
ll addL = 0, addR = 0, min_y = 0;
// Thêm hàm |x - a|
void add_abs(ll a) {
if (!L.empty() && a < L.top() + addL) {
L.push(a - addL);
L.push(a - addL);
min_y += (L.top() + addL) - a;
ll top = L.top(); L.pop();
R.push(top + addL - addR);
}
else if (!R.empty() && a > R.top() + addR) {
R.push(a - addR);
R.push(a - addR);
min_y += a - (R.top() + addR);
ll top = R.top(); R.pop();
L.push(top + addR - addL);
}
else {
L.push(a - addL);
R.push(a - addR);
}
}
// Restrict domain: chỉ giữ x sao cho
// tồn tại y cũ với |y - x| ≤ H
void chmin_slide(ll H) {
// shift các slope-changing points
addL -= H;
addR += H;
}
ll get_min() const {
return min_y;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
ll H;
cin >> n >> H;
vector<ll> S(n);
for (int i = 0; i < n; i++) {
cin >> S[i];
}
SlopeTrick st;
// Khởi tạo f_1(x) = |S[0] - x|
st.add_abs(S[0]);
for (int i = 1; i < n; i++) {
st.chmin_slide(H);
st.add_abs(S[i]);
}
cout << st.get_min() << "\n";
return 0;
}
# | 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... |