Cod sursa(job #1783333)

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

int d[MAXN+1];

struct aa{
    int ind, c, sd, cost;
}v[2*MAXN+1];

struct irt{
    int st, dr, cost;
}a[MAXN+1];

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

bool cmp(const aa &a, const aa &b){
    return (a.c < b.c);
}

bool cmp2(const irt &a, const irt &b){
    return (a.dr < b.dr);
}

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

    int k=0, n, i, x, y, t=0;

    scanf("%d", &n);

    for(i=1; i<=n; ++i)
    {
        scanf("%d%d", &x, &y);
        v[++k].ind = i;
        v[k].c = x;
        v[k].sd = 0;
        v[++k].ind = i;
        v[k].c = y;
        v[k].sd = 1;
        v[k].cost = y-x+1;
    }

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

    for(i=1; i<=k; ++i)
    {
        if(v[i].c > v[i-1].c)
        {
            t++;
            v[i].c = t;
        }else v[i].c = v[i-1].c;

        if(v[i].sd == 0)
            a[v[i].ind].st = v[i].c;
        else
        {
            a[v[i].ind].dr = v[i].c;
            a[v[i].ind].cost  = v[i].cost;
        }
    }

    std::sort(a+1, a+n+1, cmp2);

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

    printf("%d", d[a[n].dr]);

    return 0;
}