Cod sursa(job #139215)

Utilizator filipbFilip Cristian Buruiana filipb Data 19 februarie 2008 20:25:47
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <stdio.h>
#include <algorithm>
#include <set>

using namespace std;

#define maxim(a, b) ((a > b) ? a : b)
#define PII pair<int, int>
#define f first
#define s second
#define NMax 100005

int N, X[NMax<<1], D[NMax<<1], h, bst;
PII C[NMax];
set<int> A;

int cmp_pair(const PII& a, const PII& b)
{ return a.s < b.s; }

int main(void)
{
    int i, j = 1;
    set<int>::iterator it;
    
    freopen("heavymetal.in", "r", stdin);
    freopen("heavymetal.out", "w", stdout);

    scanf("%d", &N);
    for (i = 1; i <= N; i++)
    {
        scanf("%d %d", &C[i].f, &C[i].s);
        C[i].s--;
        A.insert(C[i].f);
        A.insert(C[i].s);
    }

    for (it = A.begin(); it != A.end(); ++it)
        X[++h] = *it;

    for (i = 1; i <= N; i++)
        C[i].f = lower_bound(X+1, X+h+1, C[i].f) - X,
        C[i].s = lower_bound(X+1, X+h+1, C[i].s) - X;

    sort(C+1, C+N+1, cmp_pair);

    for (i = 1; i <= h; i++)
    {
        D[i] = D[i-1];
        for (; j <= N && C[j].s == i; ++j)
            D[i] = maxim(D[i], D[C[j].f-1] + X[C[j].s] - X[C[j].f] + 1);
    }
    
    printf("%d\n", D[h]);

    return 0;
}