Submission #440642

#	Time	Username	Problem	Language	Result	Execution time	Memory
440642		peijar	Candies (JOI18_candies)	C++17	100 / 100	693 ms	28500 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]);
  }
  choices.emplace(-1e18, -1);
  choices.emplace(-1e18, nbElem);
  revChoices.emplace(-1, -1e18);
  revChoices.emplace(nbElem, -1e18);

  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});
    it--;
    int gainNext = -gain;
    gainNext += it->second;
    choices.erase({it->second, it->first});
    revChoices.erase(it++);
    gainNext += it->second;
    choices.erase({it->second, it->first});
    revChoices.erase(it);
    choices.emplace(gainNext, pos);
    revChoices.emplace(pos, gainNext);
  }
}

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