Cod sursa(job #742273)

Utilizator dariusdariusMarian Darius dariusdarius Data 29 aprilie 2012 12:22:21
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,i,p=0;
struct metal {int s,f;};
metal a[100005];
inline int cmp(metal a,metal b)
{
	return a.f<b.f;
}
int V[100005];
inline int caut(int v)
{
    int p=1,u=n,m,s=0;
    while (p<=u)
	{
        m=p+(u-p)/2;
        if (a[m].f<=v) p=m+1,s=V[m];
            else u=m-1;
    }
    return s;
}
int main ()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
    scanf("%d",&n);
	int x;
    for(i=1;i<=n;i++)
		scanf("%d%d",&a[i].s,&a[i].f);
    sort(a+1,a+n+1,cmp);
    V[1]=a[1].f-a[1].s;
    for(i=2;i<=n;i++)
	{
		x=max(V[i-1],caut(a[i].s)+a[i].f-a[i].s);
        V[i]=x;
	}
    printf("%d",V[n]);
    return 0;
}