Cod sursa(job #234614)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 21 decembrie 2008 12:49:10
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 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]);
     }
};

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]=timp[i];
          rez[i+1]=rez[i];
          int j=i;
          while (j && timp[j]>A[sir[i]])
               j--;
          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;
}