Cod sursa(job #204341)

Utilizator VmanDuta Vlad Vman Data 22 august 2008 23:44:48
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
using namespace std;
#include <cstdio>
#include <algorithm>

#define Nmax 100001

int N,i,i1,i2,nr,last;
int A[Nmax],B[Nmax],AA[Nmax],BB[Nmax],s1[Nmax],s2[Nmax], T[2*Nmax];

int cmp1(const int &a,const int &b)
{
 return A[a]<A[b];
}

int cmp2(const int &a,const int &b)
{
 return B[a]<B[b];
}

void citire()
{
 freopen("heavymetal.in","r",stdin);
 scanf("%d",&N);
 for (i=0; i<N; ++i)
     {
      scanf("%d %d",&A[i],&B[i]);
      s1[i] = s2[i] = i;
     }
}

int main()
{
 citire();
 
 sort(s1,s1+N,cmp1);
 sort(s2,s2+N,cmp2);
 //normalizare
 while (i1<N || i2<N)
       {
        if (i1 == N)
           {
            if (B[s2[i2]] == last) BB[s2[i2]] = nr;
               else { last=B[s2[i2]]; BB[s2[i2]] = (++nr); }
            ++i2;
           }
           else
           if (i2 == N)
              {
               if (A[s1[i1]] == last) AA[s1[i1]] = nr;
                  else { last=A[s1[i2]]; AA[s1[i1]] = (++nr); }
               ++i1;
              }
           else
           if (A[s1[i1]]<B[s2[i2]])
              {
               if (A[s1[i1]] == last) AA[s1[i1]] = nr;
                  else { last=A[s1[i2]]; AA[s1[i1]] = (++nr); }
               ++i1;
              }
              else
              {
            if (B[s2[i2]] == last) BB[s2[i2]] = nr;
               else { last=B[s2[i2]]; BB[s2[i2]] = (++nr); }
            ++i2;
              }
       }
 //dinamica
 for (i=0, i1=0; i<=nr; ++i)
     {
      T[i] = T[i-1];
      while (BB[s2[i1]]==i)
            {
             T[i] = max(T[i], T[AA[s2[i1]]] + B[s2[i1]]-A[s2[i1]]);
             ++i1;
            }
     }
 
 freopen("heavymetal.out","w",stdout);
 printf("%d\n",T[nr]);
 fclose(stdout);
  
 return 0;
}