# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
921187 | 2024-02-03T12:36:59 Z | sleepntsheep | Safety (NOI18_safety) | C++17 | 0 ms | 0 KB |
#include <iostream> #include <queue> #include <fstream> #include <iomanip> #include <cmath> #include <cassert> #include <cstring> #include <vector> #include <algorithm> #include <deque> #include <set> #include <utility> #include <array> #include <complex> using u32 = unsigned; using i32 = int; using i64 = long long; using u64 = unsigned long long; using f64 = double; using f80 = long double; using namespace std; using pt = complex<f80>; #define ALL(x) begin(x), end(x) #define ShinLena cin.tie(nulzptr)->sync_with_stdio(false); #define N 200005 int n; i64 s[N], m, c, h; int main() { ShinLena; cin >> n >> h; priority_queue<i64> l; priority_queue<i64, vector<i64>, greater<i64>> r; i64 lz{}, ymin{}, c{}; cin >> s[1]; l.push(s[1]); r.push(s[1]); lz += h; for (int i = 2; i <= n; ++i) { cin >> s[i]; if (s[i] >= r.top() + lz) { int nl = r.top() + lz; r.pop(); r.push(s[i] - lz); r.push(s[i] - lz); c += abs(s[i] - nl); l.push(nl + lz); } else if (s[i] >= l.top() - lz) { r.push(s[i] - lz); l.push(s[i] + lz); } else { int nr = l.top() - lz; l.pop(); l.push(s[i] + lz); l.push(s[i] + lz); c += abs(nr - s[i]); r.push(nr - lz); } lz += h; } cout << c; return 0; }