#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<ll, ll, ll> iii;
int n;
set<iii> VLR, LRV;
ll ans = 0;
int main(){
scanf("%d",&n);
for (int i = 0; i < n; i++){
ll x;
scanf("%lld",&x);
VLR.insert({x,i,i});
LRV.insert({i,i,x});
}
for (int i = 1; i <= (n+1)/2; i++){
/*for (auto x : VLR){
int a,b,c;
tie(a,b,c) = x;
printf("<%d %d %d>",a,b,c);
}
printf("<- VLR\n");
for (auto x : LRV){
int a,b,c;
tie(a,b,c) = x;
printf("<%d %d %d>",a,b,c);
}
printf("<- LRV\n");*/
ll v,l,r;
tie(v,l,r) = *(--VLR.end());
//printf("taking %lld %lld %lld\n",l,r,v);
ans += v;
int nv = -v, nl = l, nr = r;
auto it = LRV.find({l,r,v});
assert(it != LRV.end());
if (it != LRV.begin()){
auto itL = prev(it);
ll vL, lL, rL;
tie(lL, rL, vL) = *itL;
nv += vL;
VLR.erase({vL,lL,rL});
LRV.erase(itL);
nl = lL;
it = LRV.find({l,r,v});
}
if (next(it) != LRV.end()){
auto itR = next(it);
ll vR, lR, rR;
tie(lR, rR, vR) = *itR;
nv += vR;
VLR.erase({vR,lR,rR});
LRV.erase(itR);
nr = rR;
it = LRV.find({l,r,v});
}
VLR.erase(--VLR.end());
LRV.erase(it);
//printf("adding %lld %lld %lld\n",nl,nr,nv);
VLR.insert({nv,nl,nr});
LRV.insert({nl,nr,nv});
printf("%lld\n",ans);
}
}
Compilation message
candies.cpp: In function 'int main()':
candies.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
candies.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&x);
~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
