oj.uz

Submission #687862

# Submission time Handle Problem Language Result Execution time Memory
687862 2023-01-27T03:09:10 Z wenqi Candies (JOI18_candies) C++17
0 / 100
 1 ms 340 KB 
// trans rights
#include <bits/extc++.h>
using namespace std;
using ll = long long;
using base = complex<double>;
#define up(k, N) for (int k = 1; k <= N; k++)
#define down(k, N) for (int k = N; k >= 1; k--)
#define f0(A) memset(A, 0, sizeof(A))
#define f3(A) memset(A, 0x3f, sizeof(A))
#define all(A) begin(A), end(A)

int N;
ll A[200069];

int L[200069], R[200069];
bool dead[200069];

int main(int argc, const char *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> A[i];
    priority_queue<pair<ll, int>> pq;
    for (int i = 1; i <= N; i++) {
        L[i] = i - 1;
        R[i] = i + 1;
        pq.push({A[i], i});
    }
    L[0] = 0;
    R[0] = 1;
    L[N + 1] = N;
    R[N + 1] = N + 1;
    ll sum = 0;
    int cnt = 0;
    while (cnt < (N + 1) / 2) {
        auto [w, i] = pq.top();
        pq.pop();

        if (dead[i]) continue;

        sum += w;
        cnt++;
        cout << sum << '\n';

        int l = L[i], r = R[i];
        A[i] = A[l] + A[r] - A[i];
        dead[l] = dead[r] = true;
        L[i] = L[l], R[i] = R[r];
        R[L[i]] = i;
        L[R[i]] = i;
        pq.push({A[i], i});
    }
    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 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 340 KB Output isn't correct
2 Halted 0 ms 0 KB -