Cod sursa(job #249251)

Utilizator kiwiIonescu Maria kiwi Data 27 ianuarie 2009 21:55:53
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include<fstream.h>
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
long n,p,min,max;;
struct timp
	{long x,y;};
timp v[100000];
long x[100000];

long poz(long i,long j)
{int di=0,dj=1,aux;timp t;
while(i<j)
{ if(v[i].y>v[j].y){t=v[i];v[i]=v[j];v[j]=t;
			aux=di;di=dj;dj=aux;}
   i+=di;j-=dj;
}
return i;
}

void quick(int i,int j)
{if(i<j)
   {p=poz(i,j);quick(i,p-1);quick(p+1,j);}
}

int main()
{      long i,j,k=0;
 f>>n;
 while(f>>i>>j){v[++k].x=i;v[k].y=j;}
 quick(1,n);
 x[1]=v[1].y-v[1].x;min=0;
  for(i=2;i<=n;i++)
	    if(v[i].x<v[i-1].y){max=v[i].y-v[i].x;
				if(max<v[i-1].y-v[i-1].x)
				   max=v[i-1].y-v[i-1].x;
				   x[i]=min+max;}
	    else {min=x[i-1];
		  x[i]=min+v[i].y-v[i].x;}
  g<<x[n];f.close();g.close();
return 0; }