Cod sursa(job #1897536)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 1 martie 2017 15:17:33
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int Nmax = 1e5+5;

struct band
{
    int x, y;
    bool operator < (const band &a) const
    {
        return y < a.y;
    }
} a[Nmax];

int dp[Nmax], i, n;

int bs(int val, int i)
{
    int st = 1, dr = i-1, mid;

    while(st<=dr)
    {
        mid = (st+dr)/2;
        if(a[mid].y<=val) st = mid+1;
        else dr = mid-1;
    }

    return dr;
}

int main()
{
    freopen("heavymetal.in", "r", stdin);
    freopen("heavymetal.out", "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);

    for(i=1; i<=n; ++i)
        dp[i] = max(dp[i-1], dp[bs(a[i].x, i)] + a[i].y - a[i].x);

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

    return 0;
}