#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
llo n;
llo it[200001];
llo l[200001];
llo r[200001];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
for(llo i=0;i<n;i++){
cin>>it[i];
}
for(llo i=0;i<n-1;i++){
r[i]=i+1;
}
r[n-1]=-1;
l[0]=-1;
for(llo i=1;i<n;i++){
l[i]=i-1;
}
set<pair<llo,llo>> ss;
for(llo i=0;i<n;i++){
ss.insert({-it[i],i});
}
llo su=0;
for(llo i=0;i<(n+1)/2;i++){
pair<llo,llo> no=*(ss.begin());
ss.erase(no);
su+=-no.a;
llo ind=no.b;
llo kk=no.a;
if(l[ind]!=-1){
kk+=it[l[ind]];
ss.erase({-it[l[ind]],l[ind]});
}
if(r[ind]!=-1){
kk+=it[r[ind]];
ss.erase({-it[r[ind]],r[ind]});
}
ss.insert({-kk,ind});
/*cout<<l[ind]<<","<<r[ind]<<endl;
cout<<it[l[ind]]<<","<<it[ind]<<","<<it[r[ind]]<<endl;
cout<<l[l[ind]]<<":"<<r[r[ind]]<<endl;
cout<<kk<<endl;*/
if(l[ind]!=-1){
if(l[l[ind]]!=-1){
r[l[l[ind]]]=ind;
// cout<<l[l[ind]]<<"::"<<ind<<endl;
int x=l[l[ind]];
l[l[ind]]=-1;
r[l[ind]]=-1;
l[ind]=x;
}
else{
l[ind]=-1;
}
}
if(r[ind]!=-1){
if(r[r[ind]]!=-1){
l[r[r[ind]]]=ind;
int x=r[r[ind]];
l[r[ind]]=-1;
r[r[ind]]=-1;
r[ind]=x;
}
else{
r[ind]=-1;
}
}
it[ind]=kk;
cout<<su<<endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
