Pagini recente » Cod sursa (job #1034501) | Cod sursa (job #2040013) | Cod sursa (job #549770) | Cod sursa (job #1244502) | Cod sursa (job #734881)
Cod sursa(job #734881)
#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;
}