Submission #209564

#TimeUsernameProblemLanguageResultExecution timeMemory
209564Alexa2001Safety (NOI18_safety)C++17
100 / 100
72 ms5524 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pq_max = priority_queue<ll>; using pq_min = priority_queue<ll, vector<ll>, greater<ll>>; pq_max heap1; pq_min heap2; ll min_val = 0; void add(int x, ll shift) { if(x + shift >= heap1.top() && x - shift <= heap2.top()) { heap1.push(x + shift); heap2.push(x - shift); return; } if(x + shift < heap1.top()) { heap1.push(x + shift); heap1.push(x + shift); ll out = heap1.top(); heap1.pop(); min_val += out - (x + shift); heap2.push(out - 2 * shift); } else if(x - shift > heap2.top()) { heap2.push(x - shift); heap2.push(x - shift); ll out = heap2.top(); heap2.pop(); min_val += (x-shift) - out; heap1.push(out + 2 * shift); } else assert(0); } int main() { // freopen("input", "r", stdin); cin.sync_with_stdio(false); cin.tie(0); int i, x, n, H; cin >> n >> H; cin >> x; heap1.push(x); heap2.push(x); for(i=2; i<=n; ++i) { cin >> x; add(x, (ll) H * (i-1)); } cout << min_val << '\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...