Submission #544876

#	Time	Username	Problem	Language	Result	Execution time	Memory
544876		4fecta	Candies (JOI18_candies)	C++17	100 / 100	183 ms	16428 KiB

candies

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define ld long double
#define pii pair<int, int>
#define f first
#define s second
#define boost() cin.tie(0), cin.sync_with_stdio(0)

const int MN = 200005;

int n, a[MN], vis[MN], ans, take, pre[MN], nxt[MN], len[MN];

struct edge {
    int u, v, cost;
};

bool cmp(edge p, edge q) {
    return p.cost < q.cost;
}

int32_t main() {
    boost();

    cin >> n;
    n++;
    for (int i = 2; i <= n; i++) {
        cin >> a[i];
        a[i] += a[i - 1];
        pre[i] = i - 1, nxt[i] = i + 1, len[i] = a[i] - a[i - 1];
    }
    priority_queue<edge, vector<edge>, decltype(&cmp)> q(cmp);
    for (int i = 1; i < n; i++) q.push({i, i + 1, a[i + 1] - a[i]});
    while (take < n / 2) {
        edge cur = q.top();
        q.pop();
        if (vis[cur.u] || vis[cur.v]) continue;
        vis[cur.u] = vis[cur.v] = 1;
        ans += cur.cost;
        nxt[pre[cur.u]] = nxt[cur.v];
        pre[nxt[cur.v]] = pre[cur.u];
        len[nxt[cur.v]] += len[cur.u] - len[cur.v];
        take++;
        if (pre[cur.u] > 0 && nxt[cur.v] <= n) q.push({pre[cur.u], nxt[cur.v], len[nxt[cur.v]]});
        printf("%lld\n", ans);
    }

    return 0;
}

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