Cod sursa(job #996617)

Utilizator sleepaholicNeculaescu Theodor sleepaholic Data 12 septembrie 2013 13:36:19
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <cassert>
#include <cstdio>
#include <algorithm>

using namespace std;
const int nmax=1000100;
int d[nmax];

struct q
{
    int x,y;
}v[nmax/10];

bool comp(q a,q b)
{
    return a.y<b.y;
}

int main()
{
    int n=0,i=0,cnt=1;

    assert(freopen("heavymetal.in","r",stdin));
    assert(freopen("heavymetal.out","w",stdout));

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

    sort(v+1,v+n+1,comp);
    n=v[n].y;

    for (i=1; i<=n; ++i)
    {
        d[i]=d[i-1];
        while (v[cnt].y==i)
        {
            d[i]=max(d[v[cnt].x]-v[cnt].x+v[cnt].y,d[i]);
            ++cnt;
        }
    }
    printf("%d\n",d[n]);
    return 0;
}