Pagini recente » Cod sursa (job #434493) | Cod sursa (job #722565) | Cod sursa (job #554274) | Cod sursa (job #2002700) | Cod sursa (job #1239757)
#include <fstream>
#include <algorithm>
#define lmax 100005
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
long long n,nr,nrr,ma;
long long a[lmax],b[lmax],lung[lmax];
typedef struct el
{
long long p,u,l;
};
el v[lmax];
inline bool comp(el e1,el e2)
{
if (e1.u!=e2.u)
return e1.u<e2.u;
return e1.p<e2.p;
}
inline long long caut(long long x)
{
long long s=1,d=nrr;
while (s<d)
{
long long m=(s+d)/2;
if (b[m]==x)
return m;
if (b[m]>x)
d=m-1;
else
s=m+1;
}
return s;
}
inline void normalizare()
{
long long i;
for (i=1;i<=n;i++)
{
el x=v[i];
v[i].p=caut(x.p);
v[i].u=caut(x.u);
}
}
int main()
{
f>>n;
for (long long i=1;i<=n;i++)
{
f>>v[i].p>>v[i].u;
v[i].l=v[i].u-v[i].p;
a[++nr]=v[i].p;
a[++nr]=v[i].u;
}
sort(a+1,a+nr+1);
for (long long i=1;i<=nr;i++)
if (a[i]!=a[i-1])
b[++nrr]=a[i];
normalizare();
sort(v+1,v+n+1,comp);
long long nmax=v[n].u,j=1;
for (long long i=1;i<=nmax;i++)
{
lung[i]=lung[i-1];
while (v[j].u<i)
j++;
while (v[j].u==i)
{
if (lung[v[j].u]<lung[v[j].p]+v[j].l)
lung[v[j].u]=lung[v[j].p]+v[j].l;
j++;
}
}
g<<lung[nmax];
f.close();
g.close();
}