제출 #1248512

#제출 시각아이디문제언어결과실행 시간메모리
1248512Chris_BlackSafety (NOI18_safety)C++20
18 / 100
33 ms2856 KiB
//#pragma GCC optimize("Ofast") //#pragma GCC target("avx2") #include <bits/stdc++.h> #define ll long long #define vi vector<int> #define vvi vector<vi> #define pb push_back #define FOR(i, a, b) for(int i = a; i <= b; ++i) #define FORR(i, a, b) for(int i = a; i >= b; --i) #define pii pair<int, int> #define ff first #define ss second #define pll pair<ll, ll> #define vpi vector<pii> #define vvpi vector<vpi> #define vpl vector<pll> #define vvpl vector<vpl> #define vl vector<ll> #define vvl vector<vl> //#define x first //#define y second using namespace std; const int N = 1e6 + 9, LGV = 33, LGN = 21, Mod = 1e9 + 7; //const int Inf = 0x3f3f3f3f; const ll Inf = LLONG_MAX / 2; const bool test_case = false; //ifstream fin("landscape.in"); //ofstream fout("landscape.out"); //#define cin fin //#define cout fout int n, h, a[N]; ll ans = 0; ll addl = 0, addr = 0; priority_queue<int> l; priority_queue<int, vi, greater<>> r; ///move to left void shl() { ll t = r.top() + addr; r.pop(); l.push(t - addl); } ///move to right void shr() { ll t = l.top() + addl; l.pop(); r.push(t - addr); } void show() { vi v; while(!l.empty()) { v.pb(l.top() + addl); l.pop(); } reverse(v.begin(), v.end()); for(auto e : v)cout << e << ' '; cout << " | "; for(auto e : v)l.push(e - addl); v.clear(); while(!r.empty()) { cout << r.top() + addr << ' '; v.pb(r.top() + addr); r.pop(); } cout << '\n'; for(auto e : v)r.push(e - addr); } void solve() { cin >> n >> h; FOR(i, 1, n)cin >> a[i]; FOR(i, 1, n) { addl -= h, addr += h; // cout << "\n"; // show(); // cout << " | | | \n"; ll add = min(l.size() ? abs(l.top() + addl - a[i]) : 0, r.size() ? abs(r.top() + addr - a[i]) : 0); ans += add; if(l.empty() || a[i] <= l.top() + addl){ l.push(a[i] - addl); l.push(a[i] - addl); shr(); if(l.top() + addl == r.top() + addr && l.top() + addl == a[i])ans -= add; } else{ r.push(a[i] - addr); r.push(a[i] - addr); shl(); if(l.top() + addl == r.top() + addr && l.top() + addl == a[i])ans -= add; } // show(); // cout << '\n'; } cout << ans << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); int t = 1; if(test_case)cin >> t; while(t --)solve(); 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...