// wygzgyw
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
t=0; char ch=getchar(); int f=1;
while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
template <typename T> void write(T t) {
if (t<0) { putchar('-'); write(-t); return; }
if (t>9) write(t/10);
putchar('0'+t%10);
}
template <typename T> void writeln(T t) { write(t); puts(""); }
#define MP make_pair
typedef long long ll;
const int maxn=(2e5)+10;
int n,a[maxn];
bool vis[maxn];
ll val[maxn];
priority_queue<pair<ll,int> > q;
int nxt[maxn],pre[maxn];
void link(int x,int y) {
if (x) nxt[x]=y;
if (y) pre[y]=x;
}
int main() {
read(n);
for (int i=1;i<=n;i++) read(a[i]),pre[i]=i-1,nxt[i]=(i==n?0:i+1),q.push(MP(a[i],i)),val[i]=a[i];
ll ans=0;
for (int i=1;i<=(n+1)/2;i++) {
pair<ll,int> A=q.top(); q.pop();
int x=A.second;
if (vis[x]) { i--; continue; }
ans+=A.first; printf("%lld\n",ans);
int y=pre[x],z=nxt[x];
val[x]=val[y]+val[z]-val[x];
vis[y]=vis[z]=1;
link(x,nxt[z]),link(pre[y],x);
if (y&&z) q.push(MP(val[x],x));
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
