#include <bits/stdc++.h>
#define L long long
using namespace std;
L n,ans;
L a[100010],nex[100010],pre[100010],cd[100010];
struct S{
L val,loc,candy;
};
bool operator<(S a,S b){
if(a.val==b.val) return a.loc<b.loc;
return a.val>b.val;
}
bool operator==(S a,S b){
return a.val==b.val&&a.loc==b.loc;
}
set<S>st;
int main()
{
scanf("%lld",&n);
L i,j;
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
nex[i]=i+1;
pre[i]=i-1;
cd[i]=1;
S temp=(S){a[i],i,1};
st.insert(temp);
}
nex[0]=1;
pre[0]=0;
nex[n+1]=n+1;
pre[n+1]=n;
/*for(set<S>::iterator ii=st.begin();ii!=st.end();ii++)
{
printf("%lld %lld\n",ii->loc,ii->val);
}
for(j=1;j<=n;j++)
{
printf("%lld ",nex[j]);
}
puts("");
for(j=1;j<=n;j++)
{
printf("%lld ",pre[j]);
}
puts("");*/
for(i=1;i<=(n+1)/2;i++)
{
set<S>::iterator now=st.begin();
ans+=now->val;
L retur=0;
if(!now->candy) retur=1;
if(pre[now->loc]==0&&nex[now->loc]==n+1)
{
st.erase(now);
}
else if(pre[now->loc]==0)
{
//puts("1");
S nextemp=(S){a[nex[now->loc]],nex[now->loc],cd[nex[now->loc]]};
S inptemp=(S){nextemp.val-a[now->loc],now->loc,nextemp.candy-now->candy};
a[now->loc]=nextemp.val-a[now->loc];
cd[now->loc]=nextemp.candy-now->candy;
pre[nex[nex[now->loc]]]=now->loc;
nex[now->loc]=nex[nex[now->loc]];
st.erase(now);
st.erase(nextemp);
st.insert(inptemp);
}
else if(nex[now->loc]==n+1)
{
//puts("2");
S pretemp=(S){a[pre[now->loc]],pre[now->loc],cd[pre[now->loc]]};
S inptemp=(S){pretemp.val-a[now->loc],now->loc,pretemp.candy-now->candy};
a[now->loc]=pretemp.val-a[now->loc];
cd[now->loc]=pretemp.candy-now->candy;
nex[pre[pre[now->loc]]]=now->loc;
pre[now->loc]=pre[pre[now->loc]];
st.erase(now);
st.erase(pretemp);
st.insert(inptemp);
}
else
{
//puts("3");
S nextemp=(S){a[nex[now->loc]],nex[now->loc],cd[nex[now->loc]]};
S pretemp=(S){a[pre[now->loc]],pre[now->loc],cd[pre[now->loc]]};
S inptemp=(S){nextemp.val+pretemp.val-a[now->loc],now->loc,nextemp.candy+pretemp.candy-now->candy};
a[now->loc]=nextemp.val+pretemp.val-a[now->loc];
cd[now->loc]=nextemp.candy+pretemp.candy-now->candy;
/*printf("%lld %lld\n",nextemp.loc,nextemp.val);
printf("%lld %lld\n",pretemp.loc,pretemp.val);
printf("%lld %lld\n",inptemp.loc,inptemp.val);*/
pre[nex[nex[now->loc]]]=now->loc;
nex[now->loc]=nex[nex[now->loc]];
nex[pre[pre[now->loc]]]=now->loc;
pre[now->loc]=pre[pre[now->loc]];
st.erase(now);
st.erase(nextemp);
st.erase(pretemp);
st.insert(inptemp);
}
if(retur)
{
//puts("asdfasdfasd");
i--;
continue;
}
printf("%lld\n",ans);
//printf("**%lld**\n",ans);
/*for(set<S>::iterator ii=st.begin();ii!=st.end();ii++)
{
printf("%lld %lld\n",ii->loc,ii->val);
}
for(j=1;j<=n;j++)
{
printf("%lld ",nex[j]);
}
puts("");
for(j=1;j<=n;j++)
{
printf("%lld ",pre[j]);
}
puts("");
for(j=1;j<=n;j++)
{
printf("%lld ",cd[j]);
}
puts("");*/
}
}
Compilation message
candies.cpp: In function 'int main()':
candies.cpp:27:6: warning: unused variable 'j' [-Wunused-variable]
L i,j;
^
candies.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&n);
~~~~~^~~~~~~~~~~
candies.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&a[i]);
~~~~~^~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
