Submission #1198601

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198601		PakinDioxide	Candies (JOI18_candies)	C++17	0 / 100	5093 ms	320 KiB

candies

/*
    author  : PakinDioxide
    created : 09/05/2025 15:14
    task    : JOI18_candies
*/
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int mxN = 2e5+5;

ll n, a[mxN], dp[mxN];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    priority_queue <tuple <ll, int, int, int>> q;
    q.emplace(a[1], 1, 1, 1);
    while (!q.empty()) {
        auto [w, idx, cnt, t] = q.top(); q.pop();
        dp[cnt] = max(dp[cnt], w);
        if (idx == n) continue;
        q.emplace(w + a[idx+1] - t*a[idx], idx+1, cnt+1-t, 1);
        q.emplace(w, idx+1, cnt, 0);
    }
    for (int i = 1; i <= ceil(n/2.0); i++) cout << dp[i] << '\n';
}

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