Cod sursa(job #1783366)

Utilizator antanaAntonia Boca antana Data 18 octombrie 2016 22:52:16
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <cstdio>
#include <algorithm>
#define MAXN 100000

int d[MAXN+1], lg, n;

struct aa{
    int st, dr;
}v[MAXN+1];

inline int maxim(int a, int b){
    return (a > b ? a : b);
}

bool cmp(const aa &a, const aa &b){
    if(a.dr == b.dr)
        return (a.st < b.st);
    return (a.dr < b.dr);
}

inline int best(int val)
{
    int pas, ans = 0;

    for(pas = lg; pas>=1; pas>>=1)
        if(ans + pas <= n && v[ans + pas].dr <= val)
            ans += pas;

    return ans;
}

int main()
{
    freopen("heavymetal.in", "r", stdin);
    freopen("heavymetal.out", "w", stdout);

    int i, x;

    scanf("%d", &n);

    lg = 1;
    while((lg << 1) <= n)
        lg<<=1;

    for(i=1; i<=n; ++i)
        scanf("%d%d", &v[i].st, &v[i].dr);

    std::sort(v+1, v+n+1, cmp);

    for(i=1; i<=n; ++i)
    {
        x = best(v[i].st);
        d[i] = maxim(d[i-1], v[i].dr - v[i].st + d[x]);
    }

    printf("%d", d[n]);

    return 0;
}