| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 129911 |
2019-07-13T13:43:47 Z |
RockyB |
Candies (JOI18_candies) |
C++17 |
|
1070 ms |
29816 KB |
#include <bits/stdc++.h>
#define f first
#define s second
#define sz(x) (int)x.size()
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)
#define nl '\n'
#define ioi exit(0);
using namespace std;
typedef long long ll;
const int N = (int)2e5 + 7;
int n;
int a[N];
pair <ll, ll> rev(pair <ll, ll> x) {
return {x.s, x.f};
}
int main() {
ios_base :: sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#ifdef IOI
freopen ("in.txt", "r", stdin);
freopen ("A.out", "w", stdout);
#endif
cin >> n;
set < pair <ll, ll > > val, ind;
rep(i, 1, n) {
cin >> a[i];
val.insert({a[i], i});
ind.insert({i, a[i]});
}
ll ans = 0;
rep(j, 1, (n + 1) / 2) {
pair <ll, ll> ai = *val.rbegin();
val.erase(--val.end());
ind.erase(rev(ai));
ans += ai.f;
ll del = -ai.f;
bool add = 1;
{
auto it = ind.upper_bound(rev(ai));
if (it != ind.end()) {
del += it -> s;
ind.erase(it);
val.erase(rev(*it));
}
else add = 0;
}
{
auto it = ind.lower_bound(rev(ai));
if (it != ind.begin()) {
--it;
del += it -> s;
ind.erase(it);
val.erase(rev(*it));
}
else add = 0;
}
if (add) {
val.insert({del, ai.s});
ind.insert({ai.s, del});
}
cout << ans << endl;
}
ioi
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
632 KB |
Output is correct |
| 2 |
Correct |
7 ms |
632 KB |
Output is correct |
| 3 |
Correct |
7 ms |
632 KB |
Output is correct |
| 4 |
Correct |
7 ms |
632 KB |
Output is correct |
| 5 |
Correct |
7 ms |
680 KB |
Output is correct |
| 6 |
Correct |
7 ms |
632 KB |
Output is correct |
| 7 |
Correct |
7 ms |
632 KB |
Output is correct |
| 8 |
Correct |
7 ms |
632 KB |
Output is correct |
| 9 |
Correct |
7 ms |
632 KB |
Output is correct |
| 10 |
Correct |
7 ms |
632 KB |
Output is correct |
| 11 |
Correct |
8 ms |
760 KB |
Output is correct |
| 12 |
Correct |
8 ms |
632 KB |
Output is correct |
| 13 |
Correct |
8 ms |
636 KB |
Output is correct |
| 14 |
Correct |
7 ms |
632 KB |
Output is correct |
| 15 |
Correct |
8 ms |
636 KB |
Output is correct |
| 16 |
Correct |
7 ms |
636 KB |
Output is correct |
| 17 |
Correct |
7 ms |
504 KB |
Output is correct |
| 18 |
Correct |
7 ms |
632 KB |
Output is correct |
| 19 |
Correct |
7 ms |
632 KB |
Output is correct |
| 20 |
Correct |
7 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
632 KB |
Output is correct |
| 2 |
Correct |
7 ms |
632 KB |
Output is correct |
| 3 |
Correct |
7 ms |
632 KB |
Output is correct |
| 4 |
Correct |
7 ms |
632 KB |
Output is correct |
| 5 |
Correct |
7 ms |
680 KB |
Output is correct |
| 6 |
Correct |
7 ms |
632 KB |
Output is correct |
| 7 |
Correct |
7 ms |
632 KB |
Output is correct |
| 8 |
Correct |
7 ms |
632 KB |
Output is correct |
| 9 |
Correct |
7 ms |
632 KB |
Output is correct |
| 10 |
Correct |
7 ms |
632 KB |
Output is correct |
| 11 |
Correct |
8 ms |
760 KB |
Output is correct |
| 12 |
Correct |
8 ms |
632 KB |
Output is correct |
| 13 |
Correct |
8 ms |
636 KB |
Output is correct |
| 14 |
Correct |
7 ms |
632 KB |
Output is correct |
| 15 |
Correct |
8 ms |
636 KB |
Output is correct |
| 16 |
Correct |
7 ms |
636 KB |
Output is correct |
| 17 |
Correct |
7 ms |
504 KB |
Output is correct |
| 18 |
Correct |
7 ms |
632 KB |
Output is correct |
| 19 |
Correct |
7 ms |
632 KB |
Output is correct |
| 20 |
Correct |
7 ms |
632 KB |
Output is correct |
| 21 |
Correct |
1058 ms |
29664 KB |
Output is correct |
| 22 |
Correct |
955 ms |
29688 KB |
Output is correct |
| 23 |
Correct |
967 ms |
29816 KB |
Output is correct |
| 24 |
Correct |
624 ms |
29560 KB |
Output is correct |
| 25 |
Correct |
613 ms |
29476 KB |
Output is correct |
| 26 |
Correct |
647 ms |
29560 KB |
Output is correct |
| 27 |
Correct |
620 ms |
29688 KB |
Output is correct |
| 28 |
Correct |
617 ms |
29560 KB |
Output is correct |
| 29 |
Correct |
624 ms |
29688 KB |
Output is correct |
| 30 |
Correct |
636 ms |
29704 KB |
Output is correct |
| 31 |
Correct |
634 ms |
29740 KB |
Output is correct |
| 32 |
Correct |
628 ms |
29580 KB |
Output is correct |
| 33 |
Correct |
809 ms |
29392 KB |
Output is correct |
| 34 |
Correct |
765 ms |
29500 KB |
Output is correct |
| 35 |
Correct |
771 ms |
29568 KB |
Output is correct |
| 36 |
Correct |
1006 ms |
29736 KB |
Output is correct |
| 37 |
Correct |
1016 ms |
29784 KB |
Output is correct |
| 38 |
Correct |
1070 ms |
29744 KB |
Output is correct |
| 39 |
Correct |
613 ms |
29576 KB |
Output is correct |
| 40 |
Correct |
612 ms |
29432 KB |
Output is correct |
| 41 |
Correct |
611 ms |
29600 KB |
Output is correct |
| 42 |
Correct |
625 ms |
29768 KB |
Output is correct |
| 43 |
Correct |
612 ms |
29660 KB |
Output is correct |
| 44 |
Correct |
614 ms |
29812 KB |
Output is correct |
| 45 |
Correct |
638 ms |
29752 KB |
Output is correct |
| 46 |
Correct |
629 ms |
29816 KB |
Output is correct |
| 47 |
Correct |
635 ms |
29612 KB |
Output is correct |
| 48 |
Correct |
760 ms |
29380 KB |
Output is correct |
| 49 |
Correct |
767 ms |
29528 KB |
Output is correct |
| 50 |
Correct |
773 ms |
29480 KB |
Output is correct |
