Cod sursa(job #304765)

Utilizator raica_cristiraica dumitru cristian raica_cristi Data 15 aprilie 2009 11:23:00
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 kb
#include<stdio.h>
#include<algorithm>
#define LogN 18   
using namespace std;

#define dim 10001
int i,k,n;
struct heavy {int a,t;} o[dim];
int cmp (heavy a,heavy t)   
{   
    return a.a<t.a || (a.a==t.a && a.t<t.t);   
}   
int cbin (int val)   
{   
    int nr=0,put=LogN;   
    while (put--)    
        if (nr+(1<<(put))<=n)    
            if (o[nr+(1<<(put))].a<=val)   
                nr+=(1<<(put));   
    return nr;   
}   
int vec[dim],timp[dim];
/*void bubble()
{
    int x=1;
    int aux;
    while(x)
    {
            x=0;
            for(i=1;i<n;i++)
            if(a[i]>a[i+1])
            {
                           aux=a[i];
                           a[i]=a[i+1];
                           a[i+1]=aux;
                           aux=t[i];
                           t[i]=t[i+1];
                           t[i+1]=aux;
                           x=1;
                           }
                           }
}*/
void read()
{
     freopen("heavymetal.in","r",stdin);
     scanf("%d",&n);
     for(i=1;i<=n;i++)
     scanf("%d%d",&o[i].a,&o[i].t);
    // bubble();
      sort(o+1,o+n+1,cmp);   
}
void solve()
{
     read();
     int p;
    
     int max,vmax;
     for(i=1;i<=n;i++)
     {// printf("%d\n",n);
                      p=max=vmax=0;
                      for(k=1;k<i;k++)
                      {
                                      if(timp[k]>max && vec[k]<=o[i].a)
                                                 {
                                                         max=timp[k];
                                                         p=k;
                       }                                  }
                       
                      vec[i]=o[i].t;
                      timp[i]=(o[i].t-o[i].a)+timp[p];
                     /// printf("%d %d \n",timp[i],vec[i]);
                      }
                      max=0;
     for(i=1;i<=n;i++)
    // printf("%d %d \n",timp[i],vec[i]);
    if(max<timp[i])
    max=timp[i];
    
    freopen("heavymetal.out","w",stdout);
    printf("%d",max);
    
}
int main ()
{
    
    freopen("heavymetal.out","w",stdout);
    solve();
  // read();
    return 0;
}