oj.uz

Submission #893266

# Submission time Handle Problem Language Result Execution time Memory
893266 2023-12-26T19:18:34 Z box Candies (JOI18_candies) C++17
0 / 100
 1 ms 344 KB 
#include <bits/stdc++.h>
using namespace std;

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;

const int N = 200000;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<int> A(N);
    for (int &x : A) cin >> x;
    priority_queue<pair<i64, int>> paths;
    vector<int> L(N), R(N), done(N);
    for (int i = 0; i < N; i++) {
        L[i] = i - 1, R[i] = i + 1;
        paths.push({A[i], i});
    }
    int take = (N + 1) / 2;
    i64 total_cost = 0;
    for (int rep = 0; rep < take; rep++) {
        while (sz(paths) && done[paths.top().second]) paths.pop();
        assert(sz(paths));
        auto [cost, i] = paths.top(); paths.pop();
        total_cost += cost;
        cout << total_cost << '\n';
        A[i] = (L[i] < 0 ? 0 : A[L[i]]) + (R[i] >= N ? 0 : A[R[i]]) - A[i];
        if (L[i] >= 0) {
            done[L[i]] = 1;
            int u = L[L[i]];
            if (u >= 0) R[u] = i;
            L[i] = u;
        }
        if (R[i] < N) {
            done[R[i]] = 1;
            int u = R[R[i]];
            if (u < N) L[u] = i;
            R[i] = u;
        }
        paths.push({A[i], i});
    }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -