#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
candies.cpp: In function 'void solve(std::istream&, std::ostream&)':
candies.cpp:39:11: warning: unused variable 'R' [-Wunused-variable]
int R = it->first;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
640 KB |
Output is correct |
| 2 |
Correct |
7 ms |
640 KB |
Output is correct |
| 3 |
Correct |
7 ms |
640 KB |
Output is correct |
| 4 |
Correct |
6 ms |
640 KB |
Output is correct |
| 5 |
Correct |
7 ms |
640 KB |
Output is correct |
| 6 |
Correct |
7 ms |
640 KB |
Output is correct |
| 7 |
Correct |
7 ms |
640 KB |
Output is correct |
| 8 |
Correct |
7 ms |
640 KB |
Output is correct |
| 9 |
Correct |
7 ms |
640 KB |
Output is correct |
| 10 |
Correct |
6 ms |
640 KB |
Output is correct |
| 11 |
Correct |
7 ms |
640 KB |
Output is correct |
| 12 |
Correct |
7 ms |
640 KB |
Output is correct |
| 13 |
Correct |
7 ms |
640 KB |
Output is correct |
| 14 |
Correct |
7 ms |
640 KB |
Output is correct |
| 15 |
Correct |
7 ms |
640 KB |
Output is correct |
| 16 |
Correct |
7 ms |
640 KB |
Output is correct |
| 17 |
Correct |
7 ms |
640 KB |
Output is correct |
| 18 |
Correct |
7 ms |
640 KB |
Output is correct |
| 19 |
Correct |
6 ms |
640 KB |
Output is correct |
| 20 |
Correct |
6 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
640 KB |
Output is correct |
| 2 |
Correct |
7 ms |
640 KB |
Output is correct |
| 3 |
Correct |
7 ms |
640 KB |
Output is correct |
| 4 |
Correct |
6 ms |
640 KB |
Output is correct |
| 5 |
Correct |
7 ms |
640 KB |
Output is correct |
| 6 |
Correct |
7 ms |
640 KB |
Output is correct |
| 7 |
Correct |
7 ms |
640 KB |
Output is correct |
| 8 |
Correct |
7 ms |
640 KB |
Output is correct |
| 9 |
Correct |
7 ms |
640 KB |
Output is correct |
| 10 |
Correct |
6 ms |
640 KB |
Output is correct |
| 11 |
Correct |
7 ms |
640 KB |
Output is correct |
| 12 |
Correct |
7 ms |
640 KB |
Output is correct |
| 13 |
Correct |
7 ms |
640 KB |
Output is correct |
| 14 |
Correct |
7 ms |
640 KB |
Output is correct |
| 15 |
Correct |
7 ms |
640 KB |
Output is correct |
| 16 |
Correct |
7 ms |
640 KB |
Output is correct |
| 17 |
Correct |
7 ms |
640 KB |
Output is correct |
| 18 |
Correct |
7 ms |
640 KB |
Output is correct |
| 19 |
Correct |
6 ms |
640 KB |
Output is correct |
| 20 |
Correct |
6 ms |
640 KB |
Output is correct |
| 21 |
Correct |
589 ms |
29708 KB |
Output is correct |
| 22 |
Correct |
588 ms |
29688 KB |
Output is correct |
| 23 |
Correct |
589 ms |
29688 KB |
Output is correct |
| 24 |
Correct |
281 ms |
29432 KB |
Output is correct |
| 25 |
Correct |
293 ms |
29496 KB |
Output is correct |
| 26 |
Correct |
281 ms |
29432 KB |
Output is correct |
| 27 |
Correct |
307 ms |
29816 KB |
Output is correct |
| 28 |
Correct |
305 ms |
29596 KB |
Output is correct |
| 29 |
Correct |
297 ms |
29688 KB |
Output is correct |
| 30 |
Correct |
319 ms |
29688 KB |
Output is correct |
| 31 |
Correct |
315 ms |
29688 KB |
Output is correct |
| 32 |
Correct |
324 ms |
29688 KB |
Output is correct |
| 33 |
Correct |
428 ms |
29432 KB |
Output is correct |
| 34 |
Correct |
424 ms |
29432 KB |
Output is correct |
| 35 |
Correct |
426 ms |
29432 KB |
Output is correct |
| 36 |
Correct |
599 ms |
29688 KB |
Output is correct |
| 37 |
Correct |
586 ms |
29560 KB |
Output is correct |
| 38 |
Correct |
583 ms |
29560 KB |
Output is correct |
| 39 |
Correct |
280 ms |
29432 KB |
Output is correct |
| 40 |
Correct |
289 ms |
29432 KB |
Output is correct |
| 41 |
Correct |
286 ms |
29432 KB |
Output is correct |
| 42 |
Correct |
304 ms |
29688 KB |
Output is correct |
| 43 |
Correct |
306 ms |
29688 KB |
Output is correct |
| 44 |
Correct |
311 ms |
29728 KB |
Output is correct |
| 45 |
Correct |
317 ms |
29560 KB |
Output is correct |
| 46 |
Correct |
329 ms |
29816 KB |
Output is correct |
| 47 |
Correct |
321 ms |
29688 KB |
Output is correct |
| 48 |
Correct |
429 ms |
29560 KB |
Output is correct |
| 49 |
Correct |
416 ms |
29432 KB |
Output is correct |
| 50 |
Correct |
415 ms |
29468 KB |
Output is correct |
