Cod sursa(job #189809)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 18 mai 2008 14:41:43
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<fstream.h>
int car[100000],s,best[100000],ora[100000],max0=0,max,maxf=0,p,k,i,j=1,n;
struct sir {int x,y;};
sir v[100000],aux;
void pozitie(int li, int ls, int &k)

  { int i,j,di=0,dj=1,aux2;

    i=li; j=ls;
     while(i<j)

      { if(v[i].y>v[j].y)  { aux=v[i]; v[i]=v[j]; v[j]=aux;
			     aux2=di; di=dj; dj=aux2;}
    i+=di; j-=dj;
      }
   k=i;
  }

void quick ( int li, int ls)

   { if(li<ls) {pozitie (li,ls,k);
	quick(li,k-1);
	quick(k+1,ls);
	   }
   }
int main()


{

 ifstream f("heavymetal.in");
 ofstream g("heavymetal.out");

f>>n;


for(i=1;i<=n;i++)

 {f>>v[i].x>>v[i].y;
   car[v[i].y]=1;

  if(v[i].y>max0) max0=v[i].y;
 }

quick(1,n);      k=0;


for(i=1;i<=max0;i++)

  if(car[i])

     {  ora[++k]=i; p=k; max=0;


       while(v[j].y==i)

	{{ while(v[j].x<ora[--p]) ;

	  s=v[j].y-v[j].x+best[p];

	  if(s>max) max=s;
	 }
	j++;
	}

       best[j-1]=max;

       if(best[j-1] >maxf) maxf=best[j-1];
      }


g<<maxf;
f.close();
g.close();
return 0;
}