Submission #841915

#	Time	Username	Problem	Language	Result	Execution time	Memory
841915		borisAngelov	Candies (JOI18_candies)	C++17	100 / 100	95 ms	11416 KiB

candies

#include <bits/stdc++.h>

using namespace std;

const int maxn = 200005;
const long long inf = 2000000000000000000;

int n;

long long a[maxn];

// linked list
int l[maxn];
int r[maxn];

bool skip[maxn];

priority_queue<pair<long long, int>> pq;

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        pq.push(make_pair(a[i], i));

        l[i] = i - 1;
        r[i] = i + 1;
    }

    a[0] = -inf;
    a[n + 1] = -inf;

    long long ans = 0;

    for (int i = 1; i <= (n + 1) / 2; ++i)
    {
        while (skip[pq.top().second] == true)
        {
            pq.pop();
        }

        long long val = pq.top().first;
        int idx = pq.top().second;
        pq.pop();

        ans += val;
        cout << ans << "\n";

        skip[l[idx]] = true;
        skip[r[idx]] = true;

        a[idx] = a[l[idx]] + a[r[idx]] - a[idx];
        pq.push(make_pair(a[idx], idx));

        l[idx] = l[l[idx]];
        r[idx] = r[r[idx]];

        r[l[idx]] = idx;
        l[r[idx]] = idx;
    }

    return 0;
}

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