Submission #693325

#	Time	Username	Problem	Language	Result	Execution time	Memory
693325		jeroenodb	Candies (JOI18_candies)	C++14	100 / 100	333 ms	19384 KiB

candies

#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1;
const ll oo = 1e18;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n; cin >> n;
    list<ll> lst;
    struct el {
        list<ll>::iterator it;
        bool operator<(const el& o) const {
            if(*it==*o.it) {
                return it._M_node<o.it._M_node;
            }
            return *it < *o.it;
        }
    };
    multiset<el> pq;
    for(int i=0;i<n;++i) {
        int a; cin >> a;
        lst.push_back(a);
        pq.insert({prev(lst.end())});
    }
    lst.push_back(-oo);
    lst.push_front(-oo);
    ll ans=0;
    for(int i=1;i<=(n+1)/2;++i) {
        auto e = *prev(pq.end());
        pq.erase(prev(pq.end()));
        ll v = *e.it;
        ans+=v;
        auto lit = prev(e.it);
        auto rit = next(e.it);
        pq.erase({lit});
        pq.erase({rit});

        lst.erase(e.it);
        ll nv = *lit + *rit - v;
        lst.erase(rit);
        *lit=nv;
        pq.insert({lit});
        cout << ans << '\n';
        
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92