Cod sursa(job #166317)

Utilizator floringh06Florin Ghesu floringh06 Data 27 martie 2008 20:33:22
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 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];
int 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);
             while (A[crt].y == A[crt + 1].y) ++crt;
             B[i] = B[i - 1];
             if (B[crt] + A[i].y - A[i].x > B[i]) 
                     B[i] = B[crt] + A[i].y - A[i].x;
         }
         printf ("%d\n", (int) 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;
    }