| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 388904 | 2021-04-13T09:36:11 Z | denkendoemeer | Candies (JOI18_candies) | C++14 | 135 ms | 10180 KB |
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1e16
int nex[200005],pre[200005];
ll v[200005];
priority_queue<pair<ll,int>>pq;
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
int n,i;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%lld",&v[i]);
nex[i]=i+1;
pre[i]=i-1;
pq.push(make_pair(v[i],i));
}
nex[n]=0;
ll ans=0;
for(i=1;i<=(n+1)/2;i++){
while(pq.top().first!=v[pq.top().second])
pq.pop();
int x=pq.top().second,l=pre[x],r=nex[x];
ans+=v[x];
printf("%lld\n",ans);
pq.pop();
pre[nex[x]=nex[r]]=x;
nex[pre[x]=pre[l]]=x;
if (l && r)
v[x]=max((ll)-inf,v[l]+v[r]-v[x]);
else
v[x]=-inf;
v[l]=v[r]=-inf;
pq.push(make_pair(v[x],x));
}
return 0;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 332 KB | Output is correct |
| 2 | Correct | 1 ms | 332 KB | Output is correct |
| 3 | Correct | 1 ms | 332 KB | Output is correct |
| 4 | Correct | 1 ms | 324 KB | Output is correct |
| 5 | Correct | 1 ms | 332 KB | Output is correct |
| 6 | Correct | 2 ms | 332 KB | Output is correct |
| 7 | Correct | 1 ms | 320 KB | Output is correct |
| 8 | Correct | 1 ms | 332 KB | Output is correct |
| 9 | Correct | 1 ms | 332 KB | Output is correct |
| 10 | Correct | 1 ms | 332 KB | Output is correct |
| 11 | Correct | 2 ms | 408 KB | Output is correct |
| 12 | Correct | 1 ms | 332 KB | Output is correct |
| 13 | Correct | 2 ms | 324 KB | Output is correct |
| 14 | Correct | 2 ms | 332 KB | Output is correct |
| 15 | Correct | 2 ms | 460 KB | Output is correct |
| 16 | Correct | 1 ms | 332 KB | Output is correct |
| 17 | Correct | 1 ms | 324 KB | Output is correct |
| 18 | Correct | 1 ms | 332 KB | Output is correct |
| 19 | Correct | 1 ms | 332 KB | Output is correct |
| 20 | Correct | 1 ms | 332 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 332 KB | Output is correct |
| 2 | Correct | 1 ms | 332 KB | Output is correct |
| 3 | Correct | 1 ms | 332 KB | Output is correct |
| 4 | Correct | 1 ms | 324 KB | Output is correct |
| 5 | Correct | 1 ms | 332 KB | Output is correct |
| 6 | Correct | 2 ms | 332 KB | Output is correct |
| 7 | Correct | 1 ms | 320 KB | Output is correct |
| 8 | Correct | 1 ms | 332 KB | Output is correct |
| 9 | Correct | 1 ms | 332 KB | Output is correct |
| 10 | Correct | 1 ms | 332 KB | Output is correct |
| 11 | Correct | 2 ms | 408 KB | Output is correct |
| 12 | Correct | 1 ms | 332 KB | Output is correct |
| 13 | Correct | 2 ms | 324 KB | Output is correct |
| 14 | Correct | 2 ms | 332 KB | Output is correct |
| 15 | Correct | 2 ms | 460 KB | Output is correct |
| 16 | Correct | 1 ms | 332 KB | Output is correct |
| 17 | Correct | 1 ms | 324 KB | Output is correct |
| 18 | Correct | 1 ms | 332 KB | Output is correct |
| 19 | Correct | 1 ms | 332 KB | Output is correct |
| 20 | Correct | 1 ms | 332 KB | Output is correct |
| 21 | Correct | 124 ms | 10016 KB | Output is correct |
| 22 | Correct | 127 ms | 10016 KB | Output is correct |
| 23 | Correct | 118 ms | 10180 KB | Output is correct |
| 24 | Correct | 97 ms | 9912 KB | Output is correct |
| 25 | Correct | 96 ms | 9896 KB | Output is correct |
| 26 | Correct | 97 ms | 9908 KB | Output is correct |
| 27 | Correct | 101 ms | 10024 KB | Output is correct |
| 28 | Correct | 102 ms | 10012 KB | Output is correct |
| 29 | Correct | 102 ms | 10096 KB | Output is correct |
| 30 | Correct | 111 ms | 10048 KB | Output is correct |
| 31 | Correct | 104 ms | 10024 KB | Output is correct |
| 32 | Correct | 108 ms | 10120 KB | Output is correct |
| 33 | Correct | 109 ms | 9824 KB | Output is correct |
| 34 | Correct | 110 ms | 9792 KB | Output is correct |
| 35 | Correct | 114 ms | 9880 KB | Output is correct |
| 36 | Correct | 135 ms | 10104 KB | Output is correct |
| 37 | Correct | 126 ms | 10024 KB | Output is correct |
| 38 | Correct | 120 ms | 10096 KB | Output is correct |
| 39 | Correct | 100 ms | 9896 KB | Output is correct |
| 40 | Correct | 100 ms | 9848 KB | Output is correct |
| 41 | Correct | 95 ms | 9896 KB | Output is correct |
| 42 | Correct | 102 ms | 10096 KB | Output is correct |
| 43 | Correct | 105 ms | 10024 KB | Output is correct |
| 44 | Correct | 102 ms | 10096 KB | Output is correct |
| 45 | Correct | 105 ms | 10024 KB | Output is correct |
| 46 | Correct | 103 ms | 10120 KB | Output is correct |
| 47 | Correct | 102 ms | 10024 KB | Output is correct |
| 48 | Correct | 111 ms | 9892 KB | Output is correct |
| 49 | Correct | 112 ms | 9896 KB | Output is correct |
| 50 | Correct | 111 ms | 9804 KB | Output is correct |