제출 #1249109

#제출 시각아이디문제언어결과실행 시간메모리
1249109Chris_BlackSafety (NOI18_safety)C++20
100 / 100
52 ms4464 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 addl, addr; priority_queue<ll> l; priority_queue<ll, vl, greater<>> r; void rebalance() { while(l.size() > r.size()) { r.push(l.top() + addl - addr); l.pop(); } while(r.size() > l.size()) { l.push(r.top() + addr - addl); r.pop(); } } void add(ll x) { if(l.empty() || x <= l.top() + addl) l.push(x - addl); else r.push(x - addr); rebalance(); } void solve() { cin >> n >> h; FOR(i, 1, n)cin >> a[i]; ll ans = 0; FOR(i, 1, n) { addl -= h, addr += h; if(i > 1) { ll lp = l.top() + addl, rp = r.top() + addr; if(a[i] < lp)ans += lp - a[i]; else if(a[i] > rp)ans += a[i] - rp; } add(a[i]); add(a[i]); } 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...