Pagini recente » Cod sursa (job #1210676) | Cod sursa (job #883818) | Cod sursa (job #983584) | Cod sursa (job #1187694) | Cod sursa (job #139135)
Cod sursa(job #139135)
#include<stdio.h>
#include<algorithm>
#define NMAX 1000011
using namespace std;
long p,i,s[NMAX],poz,in,sf,a,j,k,l,n,m,q;
struct kkt
{
long X,Y;
};
kkt x[NMAX];
int cmpf(const kkt a,const kkt b)
{
return a.X>b.X;
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%ld",&n);
for (i=1;i<=n;i++)
scanf("%ld%ld",&x[i].X,&x[i].Y);
/* a=1;
while (a)
{
a=0;
for (i=1;i<n;i++)
if (x[i].X>x[i+1].X)
{
a=x[i].X;
x[i].X=x[i+1].X;
x[i+1].X=a;
a=x[i].Y;
x[i].Y=x[i+1].Y;
x[i+1].Y=a;
a=1;
}
} */
sort(x+1,x+n+1,cmpf);
s[1]=x[1].Y-x[1].X;
in=x[1].X;
sf=x[1].Y;
p=s[1];
for (i=2;i<=n;i++)
{
if (x[i].X>=sf)
{
s[i]=s[i-1]+x[i].Y-x[i].X;
sf=x[i].Y;
}
else
if (x[i].Y-x[i].X>x[i-1].Y-x[i-1].X)
{
sf=x[i].Y;
// s-=x[i-1].Y-x[i-1].X;
// s+=x[i].Y-x[i].X;
poz=i;
while (x[poz].Y>x[i].X) poz--;
if (s[i-1]<s[poz]+x[i].Y-x[i].X)
s[i]=s[i-1];
else
s[i]=s[poz]+x[i].Y-x[i].X;
}
else
s[i]=s[i-1];
if (p<s[i]) p=s[i];
}
printf("%ld\n",p);
return 0;
}