Submission #136504

#TimeUsernameProblemLanguageResultExecution timeMemory
136504Osama_AlkhodairyCandies (JOI18_candies)C++17
100 / 100
1046 ms27512 KiB
#include <bits/stdc++.h> using namespace std; #define finish(x) return cout << x << endl, 0 #define ll long long int n; vector <ll> a; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; a.resize(n + 2); set <int> alive; set <pair <ll, int> > s; for(int i = 1 ; i <= n ; i++){ cin >> a[i]; s.insert(make_pair(a[i], i)); alive.insert(i); } a[0] = a[n + 1] = -1e18; alive.insert(0); alive.insert(n + 1); ll ans = 0; for(int itt = 0 ; itt < (n + 1) / 2 ; itt++){ auto top = *--s.end(); s.erase(--s.end()); ans += top.first; cout << ans << endl; int pos = top.second; alive.erase(pos); a[pos] *= -1; auto it = alive.upper_bound(pos); if(it != alive.end()){ a[pos] += a[*it]; s.erase(make_pair(a[*it], *it)); alive.erase(*it); } it = alive.upper_bound(pos); if(it != alive.begin()){ it--; a[pos] += a[*it]; s.erase(make_pair(a[*it], *it)); alive.erase(*it); } alive.insert(pos); s.insert(make_pair(a[pos], pos)); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...