Cod sursa(job #742300)

Utilizator dariusdariusMarian Darius dariusdarius Data 29 aprilie 2012 14:43:11
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 STRUCT {int s,f;};
STRUCT a[100005];
inline bool cmp(STRUCT a,STRUCT b)
{
	return a.f<b.f;
}
int V[100005];
inline int caut(int v)
{
    int st=1,dr=n,med,last=0;
    while (st<=dr)
	{
        med=st+(dr-st)/2;
        if (a[med].f<=v) {st=med+1;last=V[med];}
            else dr=med-1;
    }
    return last;
}
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].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++)
		V[i]=max(V[i-1],caut(a[i].s)+a[i].f-a[i].s);
    printf("%d",V[n]);
    return 0;
}