#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;
set<llo> aa;
for(llo i=0;i<n;i++){
ss.insert({-it[i],i});
aa.insert(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;
cout<<su<<endl;
llo ind=no.b;
llo su2=no.a;
auto kk=aa.upper_bound(ind);
auto ll=aa.lower_bound(ind);
// ll--;
if(i+1==(n+1)/2){
break;
}
if(kk!=aa.end() and ll!=aa.begin()){
ll--;
// cout<<(*kk)<<","<<(*ll)<<endl;
su2+=it[*kk];
su2+=it[*ll];
// cout<<su2<<endl;
it[ind]=su2;
/* if(ss.find({-it[*kk],*kk})==ss.end() or ss.find({-it[*ll],*ll})==ss.end()){
cout<<11<<endl;
cout<<it[*kk]<<"::"<<it[*ll]<<endl;
}*/
if(ss.find({-it[*kk],*kk})==ss.end() or ss.find({-it[*ll],*ll})==ss.end()){
while(true){
continue;
}
}
ss.erase({-it[*kk],*kk});
aa.erase(*kk);
ss.erase({-it[*ll],*ll});
aa.erase(*ll);
ss.insert({-su2,ind});
}
else{
aa.erase(ind);
if(kk!=aa.end()){
if(ss.find({-it[*kk],*kk})==ss.end()){
while(true)continue;
}
ss.erase({-it[*kk],*kk});
aa.erase(*kk);
}
if(ll!=aa.begin()){
ll--;
if(ss.find({-it[*ll],*ll})==ss.end()){
while(true)continue;
}
ss.erase({-it[*ll],*ll});
aa.erase(*ll);
}
}
/*for(auto j:ss){
cout<<j.a<<"/"<<j.b<<endl;
}
cout<<endl;*/
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5045 ms |
640 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5045 ms |
640 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
