Submission #868409

#	Time	Username	Problem	Language	Result	Execution time	Memory
868409		mgl_diamond	Candies (JOI18_candies)	C++17	100 / 100	83 ms	14232 KiB

candies

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
 
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define file "input"

void setIO() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  if (fopen(file".inp", "r")) {
    freopen(file".inp", "r", stdin);
    freopen(file".out", "w", stdout);
  }
}

const ll INF = 1e18;
const int N = 2e5+5;
ll n, a[N], l[N], r[N], del[N];
priority_queue<pair<ll, ll>> pq;

int main() {
  setIO();

  cin >> n;
  foru(i, 1, n) {
    cin >> a[i];
    pq.push({a[i], i});
    l[i] = i-1;
    r[i] = i+1;
  }
  a[0] = a[n+1] = -INF;

  ll ans = 0;
  foru(z, 1, (n+1) >> 1) {
    while (del[pq.top().se]) pq.pop();

    auto [val, i] = pq.top();
    pq.pop();

    ans += val;
    cout << ans << "\n";

    a[i] = a[l[i]] + a[r[i]] - a[i];
    pq.push({a[i], i});

    del[l[i]] = del[r[i]] = 1;
    r[l[l[i]]] = i;
    l[r[r[i]]] = i;
    l[i] = l[l[i]];
    r[i] = r[r[i]];
  }
}

Compilation message (stderr)

candies.cpp: In function 'void setIO()':
candies.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen(file".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
candies.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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