Cod sursa(job #783584)

Utilizator idomiralinIdomir Alin idomiralin Data 3 septembrie 2012 13:17:33
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
# include <cstdio>
# include <algorithm>

# define max(a, b) (a < b ? b : a)

using namespace std;

struct camp
{
       int a, b;
       }interv[1000005];

int cmp(camp c, camp d)
{
    return c.a < d.a;
}

int cautbin(int x, int r)
{int rez;
     
     int l = 0, rez = 0;
     while (l <= r)
     {
           mid = (l + r) / 2;
           if (interv[mid].b <= x){ rez = mid; l = mid + 1; }
                              else r = mid - 1;
                              }
     
     return rez;
} 

int n, i, poz;
long long best[100005];
int main()
{
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    
    scanf("%d",&n);
    for (i = 1; i <= n; i++)
        scanf("%d %d",&interv[i].a,&interv[i].b);
        
    sort(interv + 1, interv + n + 1, cmp);
    
    for (i = 1; i <= n; i++)
    {
        poz = cautbin(interv[i].a, i - 1);
        best[i] = max(best[i - 1], best[poz] + interv[i].b - interv[i].a);
        }
    
    printf("%lld",best[n]);
    
return 0;
}