Submission #1000948

#TimeUsernameProblemLanguageResultExecution timeMemory
1000948vjudge1Safety (NOI18_safety)C++17
100 / 100
42 ms6016 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define ent "\n" const int maxn = 2e6 + 100; const ll INF = (ll)1e18 + 100; const int inf = 1e9 + 100; const int MOD = 1e9 + 7; const int maxl = 14; int n, h; int a[maxn]; ll sl, sr; priority_queue<ll> l; priority_queue<ll, vector<ll>, greater<ll>> r; void addl(ll x){l.push(x + sl);} ll topl(){return l.top() - sl;} void shiftl(ll x){sl += x;} void addr(ll x){r.push(x - sr);} ll topr(){return r.top() + sr;} void shiftr(ll x){sr += x;} void test(){ cin >> n >> h; for(int i = 1; i <= n ;i++){ cin >> a[i]; } addl(a[1]); addr(a[1]); shiftl(h); shiftr(h); // out(); ll sum = 0; for(int i = 2; i <= n; i++){ if(a[i] < topl()){ sum += topl() - a[i]; addr(topl()); l.pop(); addl(a[i]); addl(a[i]); } else if(a[i] > topr()){ sum += a[i] - topr(); addl(topr()); r.pop(); addr(a[i]); addr(a[i]); } else{ addl(a[i]); addr(a[i]); } shiftl(h); shiftr(h); // out(); } cout << sum; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; t = 1; while(t--) test(); cout << ent; }
#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...