Submission #700971

#TimeUsernameProblemLanguageResultExecution timeMemory
700971uroskCandies (JOI18_candies)C++14
0 / 100
3 ms980 KiB
#define here cerr<<"===========================================\n" #define dbg(x) cerr<<#x<<": "<<x<<endl; #include "bits/stdc++.h" //#include <ext/pb_ds/tree_policy.hpp> //#include <ext/pb_ds/assoc_container.hpp> #define ld double #define ll long long #define llinf 100000000000000000LL // 10^17 #define pb push_back #define popb pop_back #define fi first #define sc second #define endl '\n' #define pll pair<ll,ll> #define pld pair<ld,ld> #define sz(a) (ll)(a.size()) #define all(a) a.begin(),a.end() #define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;} #define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;} #define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0); using namespace std; #define maxn 200005 ll n; ll a[maxn]; bool cmp(pll x,pll y){return x.fi>y.fi;} multiset<pll> st; multiset<pll,decltype(&cmp)> s(cmp); void tc(){ cin >> n; for(ll i = 1;i<=n;i++) cin >> a[i]; a[0] = a[n+1] = -llinf; for(ll i = 0;i<=n+1;i++){ s.insert({a[i],i}); st.insert({i,a[i]}); } ll cnt = 0,ans = 0; while(cnt<(n+1)/2){ pll p = *s.begin(); ll i = p.sc,x = p.fi; ans+=x; cout<<ans<<endl; x = -llinf; auto it = st.lower_bound({i,x}); pll b = *it; st.erase(it); s.erase(s.find({b.sc,b.fi})); it = st.lower_bound({i,x}); pll c = *it; st.erase(it); s.erase(s.find({c.sc,c.fi})); it = st.lower_bound({i,x}); it--; pll a = *it; st.erase(it); s.erase(s.find({a.sc,a.fi})); pll d; d.fi = a.sc+c.sc-b.sc; d.sc = b.fi; s.insert(d); st.insert({d.sc,d.fi}); cnt++; } } int main(){ daj_mi_malo_vremena int t; t = 1; while(t--){ tc(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...