Submission #1227976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227976		Double_Slash	Candies (JOI18_candies)	C++20	0 / 100	3 ms	576 KiB

candies

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using pint = pair<int, int>;
 
int main() {
    int n;
    cin >> n;
    ll ps[n + 4]{};
    map<int, int> s;
    multiset<pair<ll, int>> m;
    auto calc = [&] (int l, int r) { return ps[r + 2] - ps[l] - (ps[r + 1] - ps[l + 1]); };
    for (int i = 1; i <= n; ++i) {
        cin >> ps[i + 2];
        ps[i + 2] += ps[i];
        s[i] = i;
        m.emplace(calc(i, i), i);
    }
    ll ans = 0;
    for (n = (n + 1) >> 1; n--;) {
        cout << (ans += m.rbegin()->first) << endl;
        int l = m.rbegin()->second;
        m.erase(prev(m.end()));
        auto it = s.find(l--);
        int r = it->second + 1;
        for (; next(it) != s.end(); s.erase(next(it))) {
            auto [li, ri] = *next(it);
            if (li > r) break;
            m.erase({calc(li, r = ri), li});
        }
        for (; it != s.begin(); s.erase(prev(it))) {
            auto [li, ri] = *prev(it);
            if (ri < l) break;
            m.erase({calc(l = li, ri), li});
        }
        s.erase(it);
        s[l] = r;
        m.emplace(calc(l, r), l);
    }
}

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