Cod sursa(job #234618)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 21 decembrie 2008 12:57:21
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

int A[100010],B[100010];
int timp[100010],rez[100010];
int sir[100010],n;
long maxim;

struct cmp
{
     bool operator()(const int a, const int b) const
     {
         return (B[a]<B[b]);
     }
};

int cauta(int x,int poz)
{
     int st=1,dr=poz,mij=0;
     while (st<dr)
     {
          mij=(st+dr)>>1;
          if (timp[mij]>x)
               dr=mij;
          else
               st=mij+1;
     }
while (timp[st]<=x)
     st++;
if (timp[st-1]<=x)
     return st-1;
return  0;
}

void calcul()
{
     timp[1]=B[sir[0]];
     rez[1]=B[sir[0]]-A[sir[0]];
     maxim=rez[1];
     for (int i=1;i<n;i++)
     {
          timp[i+1]=A[sir[i]]+1;
          int j=cauta(A[sir[i]],i);
          timp[i+1]=timp[i];
          rez[i+1]=rez[i];
          if (rez[i+1]<rez[j]+(B[sir[i]]-A[sir[i]]))
          {
               rez[i+1]=rez[j]+(B[sir[i]]-A[sir[i]]);
               timp[i+1]=B[sir[i]];
               maxim=rez[i+1];
          }
     }
     printf("%ld\n",maxim);
}

int main ()
{
     freopen ("heavymetal.in","r",stdin);
     freopen ("heavymetal.out","w",stdout);
     scanf ("%d",&n);
     for (int i=0;i<n;i++)
     {
          sir[i]=i;
          scanf ("%d %d",&A[i],&B[i]);
     }
     sort(sir,sir+n,cmp());
     calcul();
     return 0;
}