Submission #1051297

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051297		Sharky	Candies (JOI18_candies)	C++17	100 / 100	280 ms	27476 KiB

candies

#include <bits/stdc++.h>
using namespace std;

#define int long long

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, ans = 0;
    cin >> n;
    vector<int> a(n);
    set<int> e;
    set<pair<int, int>> st;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        e.insert(i);
        st.insert({a[i], i});
    }
    for (int it = 1; it <= (n + 1) / 2; it++) {
        auto [val, id] = *st.rbegin();
        ans += val;
        if (e.size() > 2) {
            if (id == *e.begin()) {
                st.erase({a[id], id});
                e.erase(id);
                int lb = *e.begin();
                st.erase({a[lb], lb});
                e.erase(lb);
            } else if (id == *e.rbegin()) {
                st.erase({a[id], id});
                e.erase(id);
                int lb = *e.rbegin();
                st.erase({a[lb], lb});
                e.erase(lb);
            } else {
                auto it = --e.lower_bound(id);
                int l = a[*it], ll = *it;
                it = e.upper_bound(id);
                int r = a[*it], rr = *it;
                st.erase({l, ll}); e.erase(ll);
                st.erase({r, rr}); e.erase(rr);
                st.erase({a[id], id});
                a[id] = l + r - a[id];
                st.insert({a[id], id});
            }
        }
        cout << ans << '\n';
    }
}

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