oj.uz

Submission #440637

# Submission time Handle Problem Language Result Execution time Memory
440637 2021-07-02T15:14:53 Z peijar Candies (JOI18_candies) C++17
0 / 100
 3 ms 588 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -