Cod sursa(job #166303)

Utilizator floringh06Florin Ghesu floringh06 Data 27 martie 2008 20:15:32
Problema Heavy metal Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <cstdio>
#include <algorithm>

using namespace std;

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

typedef struct
{
        int x, y;
} interv;

interv A[MAX_N];
long B[MAX_N];

int N, i;

struct cmp
    {
          bool operator () (const interv &a, const interv &b) const
          {
               if (a.y < b.y) return 1;
               return 0;
          }
    };
    
    int binary (int v)
    {
        int li = 1, lf = N, m; 
        while (li <= lf)
        {
              m = (li + lf) >> 1;
              if (A[m].y == v) break;
              if (A[m].y > v) lf = m - 1;
                 else li = m + 1;
        }
        while (A[m].y > v) return m - 1;
        return m;
    }
    
    void solve ()
    {
         int i;
         
         for (i = 1; i <= N; ++i)
         {
             int crt = binary (A[i].x);
             B[i] = B[i - 1];
             if (B[crt] + A[i].y - A[i].x > B[i]) 
                     B[i] = (long)B[crt] + A[i].y - A[i].x;
         }
         printf ("%ld\n", (long) B[N]);
    }     

    int main ()
    {
        freopen (FIN, "r", stdin);
        freopen (FOUT, "w", stdout);
        
        scanf ("%d", &N);
        for (i = 1; i <= N; ++i) scanf ("%d %d", &A[i].x, &A[i].y);
        
        sort (A + 1, A + N + 1, cmp());
        solve ();
        
        return 0;
    }