| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 709431 |
2023-03-13T14:45:05 Z |
dooompy |
Candies (JOI18_candies) |
C++17 |
|
656 ms |
28784 KB |
#include "bits/stdc++.h"
using namespace std;
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
bool is = false;
for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
return o << '}';
}
#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif
using ll = long long;
multiset<pair<ll, ll>> vals, seen;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("", "r", stdin);
// freopen("", "w", stdout);
int n; cin >> n;
for (int i = 1; i <= n; i++) {
ll a; cin >> a;
vals.insert({-a, i});
seen.insert({i, -a});
}
vals.insert({1e18, 0}); vals.insert({1e18, n + 1});
seen.insert({0, 1e18}); seen.insert({n + 1, 1e18});
ll ans = 0;
for (int i = 1; i <= (n + 1) / 2; i++) {
auto temp = vals.begin();
ans += -(temp->first);
cout << ans << "\n";
auto seentemp = seen.lower_bound({temp->second, -1e9});
seentemp--;
pair<ll, ll> a = *seentemp;
vals.erase({seentemp->second, seentemp->first});
seen.erase(seentemp++);
pair<ll, ll> b = *seentemp;
vals.erase({seentemp->second, seentemp->first});
seen.erase(seentemp++);
pair<ll, ll> c = *seentemp;
vals.erase({seentemp->second, seentemp->first});
seen.erase(seentemp++);
vals.insert({a.second + c.second - b.second, b.first});
seen.insert({b.first, a.second + c.second - b.second});
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
596 KB |
Output is correct |
| 2 |
Correct |
4 ms |
596 KB |
Output is correct |
| 3 |
Correct |
3 ms |
596 KB |
Output is correct |
| 4 |
Correct |
2 ms |
596 KB |
Output is correct |
| 5 |
Correct |
3 ms |
596 KB |
Output is correct |
| 6 |
Correct |
2 ms |
608 KB |
Output is correct |
| 7 |
Correct |
3 ms |
588 KB |
Output is correct |
| 8 |
Correct |
3 ms |
596 KB |
Output is correct |
| 9 |
Correct |
2 ms |
596 KB |
Output is correct |
| 10 |
Correct |
2 ms |
596 KB |
Output is correct |
| 11 |
Correct |
3 ms |
596 KB |
Output is correct |
| 12 |
Correct |
4 ms |
596 KB |
Output is correct |
| 13 |
Correct |
3 ms |
588 KB |
Output is correct |
| 14 |
Correct |
2 ms |
596 KB |
Output is correct |
| 15 |
Correct |
2 ms |
596 KB |
Output is correct |
| 16 |
Correct |
2 ms |
596 KB |
Output is correct |
| 17 |
Correct |
2 ms |
596 KB |
Output is correct |
| 18 |
Correct |
3 ms |
588 KB |
Output is correct |
| 19 |
Correct |
2 ms |
596 KB |
Output is correct |
| 20 |
Correct |
2 ms |
588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
596 KB |
Output is correct |
| 2 |
Correct |
4 ms |
596 KB |
Output is correct |
| 3 |
Correct |
3 ms |
596 KB |
Output is correct |
| 4 |
Correct |
2 ms |
596 KB |
Output is correct |
| 5 |
Correct |
3 ms |
596 KB |
Output is correct |
| 6 |
Correct |
2 ms |
608 KB |
Output is correct |
| 7 |
Correct |
3 ms |
588 KB |
Output is correct |
| 8 |
Correct |
3 ms |
596 KB |
Output is correct |
| 9 |
Correct |
2 ms |
596 KB |
Output is correct |
| 10 |
Correct |
2 ms |
596 KB |
Output is correct |
| 11 |
Correct |
3 ms |
596 KB |
Output is correct |
| 12 |
Correct |
4 ms |
596 KB |
Output is correct |
| 13 |
Correct |
3 ms |
588 KB |
Output is correct |
| 14 |
Correct |
2 ms |
596 KB |
Output is correct |
| 15 |
Correct |
2 ms |
596 KB |
Output is correct |
| 16 |
Correct |
2 ms |
596 KB |
Output is correct |
| 17 |
Correct |
2 ms |
596 KB |
Output is correct |
| 18 |
Correct |
3 ms |
588 KB |
Output is correct |
| 19 |
Correct |
2 ms |
596 KB |
Output is correct |
| 20 |
Correct |
2 ms |
588 KB |
Output is correct |
| 21 |
Correct |
596 ms |
28724 KB |
Output is correct |
| 22 |
Correct |
562 ms |
28744 KB |
Output is correct |
| 23 |
Correct |
626 ms |
28784 KB |
Output is correct |
| 24 |
Correct |
293 ms |
28548 KB |
Output is correct |
| 25 |
Correct |
268 ms |
28608 KB |
Output is correct |
| 26 |
Correct |
235 ms |
28552 KB |
Output is correct |
| 27 |
Correct |
245 ms |
28748 KB |
Output is correct |
| 28 |
Correct |
264 ms |
28676 KB |
Output is correct |
| 29 |
Correct |
250 ms |
28688 KB |
Output is correct |
| 30 |
Correct |
284 ms |
28688 KB |
Output is correct |
| 31 |
Correct |
270 ms |
28724 KB |
Output is correct |
| 32 |
Correct |
283 ms |
28772 KB |
Output is correct |
| 33 |
Correct |
490 ms |
28532 KB |
Output is correct |
| 34 |
Correct |
426 ms |
28536 KB |
Output is correct |
| 35 |
Correct |
418 ms |
28544 KB |
Output is correct |
| 36 |
Correct |
592 ms |
28672 KB |
Output is correct |
| 37 |
Correct |
590 ms |
28760 KB |
Output is correct |
| 38 |
Correct |
656 ms |
28716 KB |
Output is correct |
| 39 |
Correct |
267 ms |
28592 KB |
Output is correct |
| 40 |
Correct |
264 ms |
28624 KB |
Output is correct |
| 41 |
Correct |
258 ms |
28684 KB |
Output is correct |
| 42 |
Correct |
287 ms |
28756 KB |
Output is correct |
| 43 |
Correct |
271 ms |
28728 KB |
Output is correct |
| 44 |
Correct |
290 ms |
28704 KB |
Output is correct |
| 45 |
Correct |
263 ms |
28736 KB |
Output is correct |
| 46 |
Correct |
341 ms |
28748 KB |
Output is correct |
| 47 |
Correct |
273 ms |
28700 KB |
Output is correct |
| 48 |
Correct |
434 ms |
28564 KB |
Output is correct |
| 49 |
Correct |
450 ms |
28480 KB |
Output is correct |
| 50 |
Correct |
409 ms |
28520 KB |
Output is correct |
