Cod sursa(job #929619)

Utilizator alecsandrualex cuturela alecsandru Data 27 martie 2013 09:56:07
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct interval
{
    int st,dr;
};
interval a,b,v[100010];
int bs;
int n,i,j,st,dr,rez,best[100010],temp,tmax;
bool cmp(const interval &a,const interval &b)
{
    return a.dr<b.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",&st,&dr);
        a.st=st;
        a.dr=dr;
        v[i]=a;
        if(dr>tmax)
        {
            tmax=dr;
        }
    }
    sort(v+1,v+n+1,cmp);
    j=1;
    for(i=1;i<=tmax;i++)
    {
        best[i]=best[i-1];
        if(v[j].dr==i)
        {
            if(best[v[j].st]+(v[j].dr-v[j].st)>best[i])
                best[i]=best[v[j].st]+(v[j].dr-v[j].st);
            j++;
        }
    }
    printf("%d\n",best[tmax]);
    return 0;
}