Pagini recente » Cod sursa (job #672995) | Cod sursa (job #2071705) | Cod sursa (job #697998) | Cod sursa (job #3257082) | Cod sursa (job #278298)
Cod sursa(job #278298)
#include<stdio.h>
FILE*f=fopen("oo.in","r");
FILE*g=fopen("oo.out","w");
typedef struct{int x,y,s;}OO;
OO a[100001],aux;
long n;
int b[100001];
void citire()
{
long i;
fscanf(f,"%ld",&n);
for(i=0;i<n;i++)
{
fscanf(f,"%d",&b[i]);
if(i>=1) {
a[i-1].s=b[i]+b[i-1];
a[i-1].x=i-1;
a[i-1].y=i;
}
}
a[n-1].s=b[n-1]+b[0];
a[n-1].x=0;
a[n-1].y=n-1;
}
long divide(long p,long q)
{
long st=p,dr=q;
aux=a[p];
while(st<dr)
{
while(st<dr && a[dr].s>=aux.s) dr--;
a[st]=a[dr];
while(st<dr && a[st].s<=aux.s) st++;
a[dr]=a[st];
}
a[st]=aux;
return st;
}
void qsort(long p,long q)
{
long m=divide(p,q);
if(m-1>p) qsort(p,m-1);
if(m+1<q) qsort(m+1,q);
}
int main()
{
long S=0,i;
citire();
qsort(0,n-1);
for(i=n-1;i>=0;i--)
if(b[a[i].x]>=0 && b[a[i].y]>=0) {
S+=a[i].s;
b[a[i].x]=-1;
b[a[i].y]=-1;
if(a[i].x==0) b[n-1]=-1;
else b[a[i].x-1]=-1;
if(a[i].y==n-1) b[0]=-1;
else b[a[i].y+1]=-1;
}
fprintf(g,"%ld",S);
return 0;
}