Submission #232616

#	Time	Username	Problem	Language	Result	Execution time	Memory
232616		AlexLuchianov	Candies (JOI18_candies)	C++14	100 / 100	622 ms	27512 KiB

candies

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <set>

using namespace std;

using ll = long long;
int const nmax = 200000;
ll v[1 + nmax];

set<int> myset;
set<pair<ll,int>> pq;

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n;
  cin >> n;
  ll result = 0;
  for(int i = 1;i <= n; i++){
    cin >> v[i];
    myset.insert(i);
    pq.insert({v[i], i});
  }
  int lim = (n + 1) / 2;

  for(int i = 1;i <= lim; i++){
    set<pair<ll, int>>::iterator itpq = pq.end();
    itpq--;

    result += itpq->first;
    cout << result << '\n';
    int id = itpq->second;
    pq.erase(itpq);

    set<int>::iterator it, it2;
    myset.erase(id);
    it = myset.lower_bound(id);

    if(it == myset.end()){
      if(0 < myset.size()) {
        it--;
        pq.erase({v[*it], *it});
        myset.erase(it);
      }
      continue;
    }
    if(it == myset.begin()){
      pq.erase({v[*it], *it});
      myset.erase(it);
      continue;
    }
    it2 = it;
    it2--;

    v[id] = v[*it2] + v[*it] - v[id];
    pq.erase({v[*it2], *it2});
    pq.erase({v[*it], *it});
    pq.insert({v[id], id});

    myset.erase(it);
    myset.erase(it2);
    myset.insert(id);
  }
  cout << '\n';
  return 0;
}

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