#include <iostream>
#include <fstream>
#include <queue>
#include <climits>
using namespace std;
const int nmax=200005;
const long long inf=1LL*100000*100000*100000*10;
priority_queue< pair<long long,int> > pq;
int n,i,j,poz,st,dr;
long long val,ans,v1,v2;
long long v[nmax];
int tt[nmax],rg[nmax],l[nmax],r[nmax];
int main()
{
//freopen("data.in","r",stdin);
ios_base::sync_with_stdio(false);
cin>>n;
for(i=1;i<=n;i++)
{
cin>>v[i];
pq.push({v[i],i});
l[i]=i-1;r[i]=i+1;
}
int cnt=0;
while((!pq.empty())&&cnt<(n+1)/2)
{
val=pq.top().first;
poz=pq.top().second;
pq.pop();
if(v[poz]!=val) continue;
cnt+=1;
st=l[poz];dr=r[poz];
v1=v2=0;
v[poz]=-inf;
v1=v[st];
l[poz]=l[st];
r[l[poz]]=poz;
v[st]=-inf;
v2=v[dr];
r[poz]=r[dr];
l[r[poz]]=poz;
v[dr]=-inf;
ans+=val;
if(st&&dr<=n)
{
v[poz]=v1+v2-val;
v[poz]=max(v[poz],-inf);
pq.push({v[poz],poz});
}
cout<<ans<<'\n';
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
3 ms |
504 KB |
Output is correct |
| 3 |
Correct |
3 ms |
376 KB |
Output is correct |
| 4 |
Correct |
3 ms |
504 KB |
Output is correct |
| 5 |
Correct |
3 ms |
504 KB |
Output is correct |
| 6 |
Correct |
3 ms |
504 KB |
Output is correct |
| 7 |
Correct |
2 ms |
504 KB |
Output is correct |
| 8 |
Correct |
3 ms |
504 KB |
Output is correct |
| 9 |
Correct |
3 ms |
500 KB |
Output is correct |
| 10 |
Correct |
3 ms |
504 KB |
Output is correct |
| 11 |
Correct |
3 ms |
504 KB |
Output is correct |
| 12 |
Correct |
3 ms |
504 KB |
Output is correct |
| 13 |
Correct |
3 ms |
504 KB |
Output is correct |
| 14 |
Correct |
3 ms |
504 KB |
Output is correct |
| 15 |
Correct |
3 ms |
504 KB |
Output is correct |
| 16 |
Correct |
3 ms |
504 KB |
Output is correct |
| 17 |
Correct |
3 ms |
504 KB |
Output is correct |
| 18 |
Correct |
3 ms |
504 KB |
Output is correct |
| 19 |
Correct |
3 ms |
504 KB |
Output is correct |
| 20 |
Correct |
3 ms |
504 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
3 ms |
504 KB |
Output is correct |
| 3 |
Correct |
3 ms |
376 KB |
Output is correct |
| 4 |
Correct |
3 ms |
504 KB |
Output is correct |
| 5 |
Correct |
3 ms |
504 KB |
Output is correct |
| 6 |
Correct |
3 ms |
504 KB |
Output is correct |
| 7 |
Correct |
2 ms |
504 KB |
Output is correct |
| 8 |
Correct |
3 ms |
504 KB |
Output is correct |
| 9 |
Correct |
3 ms |
500 KB |
Output is correct |
| 10 |
Correct |
3 ms |
504 KB |
Output is correct |
| 11 |
Correct |
3 ms |
504 KB |
Output is correct |
| 12 |
Correct |
3 ms |
504 KB |
Output is correct |
| 13 |
Correct |
3 ms |
504 KB |
Output is correct |
| 14 |
Correct |
3 ms |
504 KB |
Output is correct |
| 15 |
Correct |
3 ms |
504 KB |
Output is correct |
| 16 |
Correct |
3 ms |
504 KB |
Output is correct |
| 17 |
Correct |
3 ms |
504 KB |
Output is correct |
| 18 |
Correct |
3 ms |
504 KB |
Output is correct |
| 19 |
Correct |
3 ms |
504 KB |
Output is correct |
| 20 |
Correct |
3 ms |
504 KB |
Output is correct |
| 21 |
Correct |
121 ms |
10208 KB |
Output is correct |
| 22 |
Correct |
121 ms |
10184 KB |
Output is correct |
| 23 |
Correct |
134 ms |
10196 KB |
Output is correct |
| 24 |
Correct |
92 ms |
10060 KB |
Output is correct |
| 25 |
Correct |
88 ms |
10080 KB |
Output is correct |
| 26 |
Correct |
88 ms |
9956 KB |
Output is correct |
| 27 |
Correct |
107 ms |
10188 KB |
Output is correct |
| 28 |
Correct |
102 ms |
10108 KB |
Output is correct |
| 29 |
Correct |
99 ms |
10208 KB |
Output is correct |
| 30 |
Correct |
101 ms |
10208 KB |
Output is correct |
| 31 |
Correct |
110 ms |
10208 KB |
Output is correct |
| 32 |
Correct |
99 ms |
10208 KB |
Output is correct |
| 33 |
Correct |
112 ms |
10012 KB |
Output is correct |
| 34 |
Correct |
111 ms |
10020 KB |
Output is correct |
| 35 |
Correct |
115 ms |
9992 KB |
Output is correct |
| 36 |
Correct |
130 ms |
10148 KB |
Output is correct |
| 37 |
Correct |
130 ms |
10188 KB |
Output is correct |
| 38 |
Correct |
127 ms |
10144 KB |
Output is correct |
| 39 |
Correct |
96 ms |
10088 KB |
Output is correct |
| 40 |
Correct |
88 ms |
10108 KB |
Output is correct |
| 41 |
Correct |
85 ms |
10048 KB |
Output is correct |
| 42 |
Correct |
96 ms |
10208 KB |
Output is correct |
| 43 |
Correct |
103 ms |
10208 KB |
Output is correct |
| 44 |
Correct |
102 ms |
10156 KB |
Output is correct |
| 45 |
Correct |
99 ms |
10180 KB |
Output is correct |
| 46 |
Correct |
96 ms |
10180 KB |
Output is correct |
| 47 |
Correct |
96 ms |
10208 KB |
Output is correct |
| 48 |
Correct |
103 ms |
9992 KB |
Output is correct |
| 49 |
Correct |
103 ms |
10032 KB |
Output is correct |
| 50 |
Correct |
100 ms |
9908 KB |
Output is correct |
