Cod sursa(job #278298)

Utilizator ghiutaalexGhiuta Alex ghiutaalex Data 12 martie 2009 11:06:56
Problema Oo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#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;
}