Submission #1182753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182753		NoMercy	Candies (JOI18_candies)	C++20	100 / 100	317 ms	19156 KiB

candies

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

typedef long long ll;

int32_t main () {

    ios_base::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0); 

    int N;
    cin >> N;
    vector<ll> arr(N), L(N, -1), R(N, -1);
    multiset<array<ll, 2>> s;
    for (int i = 0;i < N;i ++) {
        cin >> arr[i];
        s.insert({arr[i], i});
        if (i - 1 >= 0) L[i] = i - 1;
        if (i + 1 < N) R[i] = i + 1;
    }

    ll sum = 0;
    for (int i = 1;i <= (N + 1) / 2;i ++) {
        assert(s.size() > 0);
        auto it = *s.rbegin();
        s.erase(-- s.end());
        sum += (it)[0];
        cout << sum << "\n";

        it[0] = -1 * it[0];
        if (L[it[1]] != -1) {
            s.erase(s.find({arr[L[it[1]]], L[it[1]]}));
            it[0] += arr[L[it[1]]];
            if (L[L[it[1]]] != -1) R[L[L[it[1]]]] = it[1];
            L[it[1]] = L[L[it[1]]];
        } else {
            it[0] += (-1e15);
        }
        if (R[it[1]] != -1) {
            s.erase(s.find({arr[R[it[1]]], R[it[1]]}));
            it[0] += arr[R[it[1]]];
            if (R[R[it[1]]] != -1) L[R[R[it[1]]]] = it[1];
            R[it[1]] = R[R[it[1]]];
        } else {
            it[0] += (-1e15);
        }
        arr[it[1]] = it[0];
        s.insert({arr[it[1]], it[1]});
    }
}

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