Cod sursa(job #249849)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 29 ianuarie 2009 13:35:21
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include<fstream.h>

int norm[100010],best[100010],i,j,p,k,n;

struct sir {int x,y;} v[100010];

int poz(int i,int j)

{ int di,dj,aux;
  sir aux2;

  di=0; dj=1;

  while(i<j)

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

      i+=di; j-=dj;
   }
 return i;
}

void quick(int s, int d)

 { if(s<d)

  { int p=poz(s,d);

     quick(s,p-1);
     quick(p+1,d);
  }
 }

int cautare(int val)

 { int s,d,m;

  s=1; d=n; m=(s+d)>>1;

   while(s<d)

    {
     if(v[m].y>val) d=m-1;

      else if(v[m].y<val) s=m+1;

       else break;

     m=(s+d)>>1;
    }

  return m;
 }

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;

quick(1,n);

k=1; norm[1]=1;

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

  if(v[i].y==v[i-1].y) norm[i]=norm[i-1];

      else {k++; norm[i]=k;}

best[1]=v[1].y-v[1].x;


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


 { best[i]=best[i-1];

   j=i;

   while(norm[j]==norm[i])

    { p=cautare(v[j].x);

     if(best[i]<best[p]+v[j].y-v[j].x)

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

     j--;
    }
  }

g<<best[n];

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