Submission #977844

#TimeUsernameProblemLanguageResultExecution timeMemory
977844phoenixSafety (NOI18_safety)C++17
3 / 100
2054 ms1860 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 200'200; int n; ll h; ll s[N]; void solve() { cin >> n >> h; for (int i = 1; i <= n; i++) cin >> s[i]; set<ll> t1, t2; t1.insert(s[1]); t2.insert(s[1]); ll base = 0; for (int i = 2; i <= n; i++) { set<ll> st; { for (ll c : t1) st.insert(c - h); t1 = st; st.clear(); } { for (ll c : t2) st.insert(c + h); t2 = st; st.clear(); } ll l = *(--t1.end()), r = *t2.begin(); if (l <= s[i] && s[i] <= r) { t1.insert(s[i]); t2.insert(s[i]); } else if (s[i] < l) { t1.insert(s[i]); t1.insert(s[i]); t1.erase(l); t2.insert(l); base += l - s[i]; } else { t2.insert(s[i]); t2.insert(s[i]); t2.erase(r); t1.insert(r); base += s[i] - r; } } cout << base; } int main() { ios::sync_with_stdio(0); cin.tie(0); int test_cases = 1; // cin >> test_cases; while (test_cases-->0) { solve(); } }
#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...