// 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 ll INF=1e18;
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; val[0]=-INF;
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 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
456 KB |
Output is correct |
| 3 |
Correct |
1 ms |
428 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
468 KB |
Output is correct |
| 14 |
Correct |
1 ms |
468 KB |
Output is correct |
| 15 |
Correct |
1 ms |
460 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
468 KB |
Output is correct |
| 18 |
Correct |
1 ms |
468 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
456 KB |
Output is correct |
| 3 |
Correct |
1 ms |
428 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
468 KB |
Output is correct |
| 14 |
Correct |
1 ms |
468 KB |
Output is correct |
| 15 |
Correct |
1 ms |
460 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
468 KB |
Output is correct |
| 18 |
Correct |
1 ms |
468 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
468 KB |
Output is correct |
| 21 |
Correct |
79 ms |
11036 KB |
Output is correct |
| 22 |
Correct |
82 ms |
11080 KB |
Output is correct |
| 23 |
Correct |
108 ms |
10984 KB |
Output is correct |
| 24 |
Correct |
63 ms |
10932 KB |
Output is correct |
| 25 |
Correct |
60 ms |
10928 KB |
Output is correct |
| 26 |
Correct |
63 ms |
10928 KB |
Output is correct |
| 27 |
Correct |
80 ms |
11060 KB |
Output is correct |
| 28 |
Correct |
73 ms |
11100 KB |
Output is correct |
| 29 |
Correct |
88 ms |
11096 KB |
Output is correct |
| 30 |
Correct |
72 ms |
11072 KB |
Output is correct |
| 31 |
Correct |
71 ms |
11056 KB |
Output is correct |
| 32 |
Correct |
79 ms |
11064 KB |
Output is correct |
| 33 |
Correct |
72 ms |
10856 KB |
Output is correct |
| 34 |
Correct |
76 ms |
10760 KB |
Output is correct |
| 35 |
Correct |
85 ms |
10836 KB |
Output is correct |
| 36 |
Correct |
86 ms |
11016 KB |
Output is correct |
| 37 |
Correct |
80 ms |
11000 KB |
Output is correct |
| 38 |
Correct |
87 ms |
10996 KB |
Output is correct |
| 39 |
Correct |
63 ms |
10864 KB |
Output is correct |
| 40 |
Correct |
66 ms |
10904 KB |
Output is correct |
| 41 |
Correct |
60 ms |
10816 KB |
Output is correct |
| 42 |
Correct |
75 ms |
11032 KB |
Output is correct |
| 43 |
Correct |
72 ms |
11184 KB |
Output is correct |
| 44 |
Correct |
73 ms |
11060 KB |
Output is correct |
| 45 |
Correct |
70 ms |
11184 KB |
Output is correct |
| 46 |
Correct |
90 ms |
11084 KB |
Output is correct |
| 47 |
Correct |
71 ms |
11092 KB |
Output is correct |
| 48 |
Correct |
75 ms |
10772 KB |
Output is correct |
| 49 |
Correct |
72 ms |
10888 KB |
Output is correct |
| 50 |
Correct |
91 ms |
10792 KB |
Output is correct |
