Submission #440637

#	Time	Username	Problem	Language	Result	Execution time	Memory
440637		peijar	Candies (JOI18_candies)	C++17	0 / 100	3 ms	588 KiB

candies

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbElem;
  cin >> nbElem;

  vector<int> val(nbElem);
  for (auto &v : val)
    cin >> v;

  set<pair<int, int>> choices, revChoices;
  for (int iEl = 0; iEl < nbElem; ++iEl) {
    choices.emplace(val[iEl], iEl);
    revChoices.emplace(iEl, val[iEl]);
  }

  int curRet = 0;
  for (int prend = 1; prend <= (nbElem + 1) / 2; ++prend) {
    auto [gain, pos] = *choices.rbegin();
    curRet += gain;
    cout << curRet << '\n';
    if (prend + 1 > (nbElem + 1) / 2)
      break;

    choices.erase({gain, pos});
    revChoices.erase({pos, gain});
    auto it = revChoices.lower_bound({pos, -(int)1e18});
    int gainNext = -gain;
    if (it != revChoices.end()) {
      gainNext += it->second;
      choices.erase({it->second, it->first});
      revChoices.erase(it);
    }
    it = revChoices.lower_bound({pos, -(int)1e18});
    if (it != revChoices.begin()) {
      it--;
      gainNext += it->second;
      choices.erase({it->second, it->first});
      revChoices.erase(it);
    }
    choices.emplace(gainNext, pos);
    revChoices.emplace(pos, gainNext);
  }
}

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