Cod sursa(job #734881)

Utilizator robertpoeRobert Poenaru robertpoe Data 15 aprilie 2012 09:08:09
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <fstream>
#include <algorithm>
#define xxl long long
#define dim 100001
#define FOR for(i=1;i<=n;i++)
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
xxl n,i,p=0;
struct metal
{
	xxl s,f;
};metal a[dim];
inline int cmp(metal a,metal b)
{
	return a.f<b.f;
}
xxl V[dim];
inline xxl caut(xxl v)
{
    xxl 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 ()
{
    f>>n;
    FOR
		f>>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++)
	{
		int x=max(V[i-1],caut(a[i].s)+a[i].f-a[i].s);
        V[i]=x;
	}
    g<<V[n];
    return 0;
}