Cod sursa(job #927997)

Utilizator alecsandrualex cuturela alecsandru Data 26 martie 2013 10:21:39
Problema Heavy metal Scor 40
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 n,i,j,st,dr,rez,c[100010],temp;
bool cmp(const interval &a,const interval &b)
{
    return a.st<b.st;
}
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;
    }
    sort(v+1,v+n+1,cmp);
    for(i=1;i<=n;i++)
    {
        a=v[i];
        for(j=i-1;j>=0;j--)
        {
            b=v[j];
            if(b.dr<=a.st)
            {
                temp=c[j]+a.dr-a.st;
                if(temp>c[i])
                    c[i]=temp;
                if(temp>rez)
                    rez=temp;
            }
        }
    }
    printf("%d\n",rez);
    return 0;
}