Submission #1248200

#TimeUsernameProblemLanguageResultExecution timeMemory
1248200zhangspicyuwuSafety (NOI18_safety)C++20
100 / 100
38 ms5228 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...