Submission #225413

#	Time	Username	Problem	Language	Result	Execution time	Memory
225413		gilles_deleuze	Candies (JOI18_candies)	C++17	100 / 100	599 ms	29816 KiB

candies

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

void solve(std::istream &in, std::ostream &out);

int main() {
#ifdef LOCAL
  freopen("../IO/f.in", "r", stdin);
//  freopen("../IO/f.out", "w", stdout);
#else
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
#endif
  solve(std::cin, std::cout);
  return 0;
}


void solve(std::istream &in, std::ostream &out) {
  int n;
  in >> n;
  vector<int> a(n);
  for (int &i : a) in >> i;
  set<pair<int64_t, int>, greater<>> costs;
  set<pair<int, int64_t>> segs;
  for (int i = 0; i < n; ++i) {
    costs.emplace(a[i], i);
    segs.emplace(i, a[i]);
  }
  int64_t sum = 0;
  for (int iteration = 0; iteration < (n + 1) / 2; ++iteration) {
    pair<int64_t, int> f = *costs.begin();
    sum += f.first;
    auto it = segs.find(make_pair(f.second, f.first));
    if (it != segs.begin() && it != (--segs.end())) {
      int64_t new_cost = -f.first;
      new_cost += (++it)->second;
      int R = it->first;
      auto nxt = *it;
      costs.erase(make_pair(it->second, it->first));
      new_cost += (--(--it))->second;
      int L = it->first;
      auto prv = *it;
      costs.erase(make_pair(it->second, it->first));
      costs.erase(f);
      segs.erase(++it);
      segs.erase(nxt);
      segs.erase(prv);
      costs.emplace(new_cost, L);
      segs.emplace(L, new_cost);
    } else if (it == segs.begin()) {
      segs.erase(segs.begin());
      if (!segs.empty()) {
        costs.erase(make_pair(segs.begin()->second, segs.begin()->first));
        segs.erase(segs.begin());
      }
      costs.erase(f);
    } else {
      segs.erase(--segs.end());
      if (!segs.empty()) {
        auto itt = --segs.end();
        costs.erase(make_pair(itt->second, itt->first));
        segs.erase(itt);
      }
      costs.erase(f);
    }
    out << sum << '\n';
  }
}

Compilation message (stderr)

candies.cpp: In function 'void solve(std::istream&, std::ostream&)':
candies.cpp:39:11: warning: unused variable 'R' [-Wunused-variable]
       int R = it->first;
           ^

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