Cod sursa(job #167269)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 29 martie 2008 13:11:20
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
# include <stdio.h>

using namespace std;

# define FIN "heavymetal.in"
# define FOUT "heavymetal.out"
# define MAX_N 100001

typedef struct trio
{
    long a,b,s;
};

long n,i;
trio v[MAX_N];

void down(long i, long n)
{
 long fiu=i << 1,tata=i;
 trio l=v[i];;
 while (fiu<=n)
   {
    if (fiu<n && v[fiu].b<v[fiu+1].b) fiu++;
    if (l.b<v[fiu].b)
      {
       v[tata]=v[fiu];
       tata=fiu;
       fiu=fiu << 1;
      }
    else fiu=n+1;
   }
 v[tata]=l;
}

void heapsort()
{
 long i,aux;
 trio m;
 aux=n >> 1;
 for (i = aux; i >= 1; i--)
   down(1,n);
 for (i = n; i > 1; i--)
   {
    m=v[i];
    v[i]=v[1];
    v[1]=m;
    down(1,i-1);
   }
}

long search(long st, long dr, long vl)
{
 long mij,poz=0,max=0;
 while (st<=dr)
   { 
    mij=(st+dr)>>1;
    if (v[mij].b<=vl)
      {
       if (v[mij].s>max)
         {
          max=v[mij].s;
          poz=mij;
         }
       st=mij+1;
      }
    else dr=mij-1;
   }
 return poz;
}

void solve()
{
 long aux,i;
 for (i=1; i<=n; i++)
   {
    aux=search(1,i-1,v[i].a);
    if (v[aux].s+v[i].b-v[i].a>v[i-1].s) 
      v[i].s=v[aux].s+v[i].b-v[i].a;
    else
      v[i].s=v[i-1].s;
   }
 printf("%ld",v[n].s);
}

int main()
{
 freopen(FIN,"r",stdin);
 freopen(FOUT,"w",stdout);
 scanf("%ld",&n);
 for (i=1; i<=n; i++)
   scanf("%ld %ld",&v[i].a,&v[i].b);
 heapsort();
 solve();
 return 0;
}