Submission #158506

#TimeUsernameProblemLanguageResultExecution timeMemory
158506gs18103Safety (NOI18_safety)C++14
3 / 100
65 ms4184 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll s[202020]; multiset <ll> R; multiset <ll, greater <ll> > L; 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 l = s[1], r = s[1], ans = 0; L.insert(s[1]), R.insert(s[1]); for(int i = 2; i <= n; i++) { l -= h, r += h; if(s[i] < l) { ans += l - s[i]; R.insert((*R.begin())-r+l); L.insert(s[i] + h * (i - 1)); L.insert(s[i] + h * (i - 1)); ll d = *L.begin() - *(next(L.begin())); r = l; l = l - d; L.erase(*L.begin()); } else if(s[i] > r) { ans += s[i] - r; L.insert((*L.begin())+r-l); R.insert(s[i] - h * (i - 1)); R.insert(s[i] - h * (i - 1)); ll d = *(next(R.begin())) - *(R.begin()); l = r; r = l + d; R.erase(*R.begin()); } else { l = r = s[i]; L.insert(s[i] + h * (i - 1)); R.insert(s[i] - h * (i - 1)); } } cout << ans; }
#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...