Submission #963911

#	Time	Username	Problem	Language	Result	Execution time	Memory
963911		abczz	Candies (JOI18_candies)	C++14	100 / 100	140 ms	11984 KiB

candies

#include <iostream>
#include <queue>
#include <array>
#define ll long long
 
using namespace std;
 
priority_queue <array<ll, 2>> pq;
bool B[200000];
ll n, f, A[200000], pre[200000], nx[200000];
 
void linkerase(ll u) {
  B[u] = 1;
  if (pre[u] != -1) nx[pre[u]] = nx[u];
  if (nx[u] < n) pre[nx[u]] = pre[u];
}
 
int main() {
  cin >> n;
  for (int i=0; i<n; ++i) {
    cin >> A[i];
    pre[i] = i-1, nx[i] = i+1;
    pq.push({A[i], i});
  }
  for (int i=0; i<(n+1)/2; ++i) {
    while (true) {
      auto [w, u] = pq.top();
      pq.pop();
      if (B[u]) continue;
      f += w;
      if (pre[u] != -1 && nx[u] < n) {
        pq.push({A[pre[u]]+A[nx[u]]-w, u});
        A[u] = A[pre[u]]+A[nx[u]]-w;
      }
      else linkerase(u);
      if (pre[u] != -1) linkerase(pre[u]);
      if (nx[u] < n) linkerase(nx[u]);
      cout << f << '\n';
      break;
    }
  }
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:27:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |       auto [w, u] = pq.top();
      |            ^

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