Submission #1035082

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035082		juicy	Candies (JOI18_candies)	C++17	100 / 100	72 ms	10480 KiB

candies

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5;
const long long inf = 1e18;

int n;
int L[N], R[N];
long long a[N];
bool tog[N];

void app(int u) {
  tog[u] = 1;
  L[R[u]] = L[u];
  R[L[u]] = R[u];
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n;
  priority_queue<pair<long long, int>> pq;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    L[i] = i - 1, R[i] = i + 1;
    pq.push({a[i], i});
  }
  a[0] = a[n + 1] = -inf;
  R[n + 1] = n + 1;
  long long res = 0;
  for (int i = 1; i <= (n + 1) / 2; ++i) {
    while (pq.size() && tog[pq.top().second]) {
      pq.pop();
    }
    cout << (res += pq.top().first) << "\n";
    int u = pq.top().second;
    pq.pop();
    int lt = L[u], rt = R[u];
    pq.push({a[u] = a[lt] + a[rt] - a[u], u});
    app(lt);
    app(rt);
  }
  return 0;
}

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