Pagini recente » Cod sursa (job #2404060) | Cod sursa (job #2875615) | Cod sursa (job #590195) | Cod sursa (job #2072107) | Cod sursa (job #140658)
Cod sursa(job #140658)
#include<stdio.h>
#include<algorithm>
#define NMAX 101001
using namespace std;
long p,i,y[NMAX],poz,in,sf,a,j,k,l,n,m,q;
struct kkt
{
long X,Y;
};
kkt x[NMAX],aux;
int cmpf(const kkt a,const kkt b)
{
return a.Y>b.Y;
}
long mx(long a,long b)
{
if (a>b) return a;
return b;
}
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].Y>x[i+1].Y)||(x[i].Y==x[i+1].Y&&x[i].X<x[i+1].X))
{
aux=x[i];
x[i]=x[i+1];
x[i+1]=aux;
a=1;
}
} */
/* for (i=1;i<=10;i++)
{
y[i]=y[i-1];
for (j=1;j<=n;j++)
if (x[j].Y==i)
y[i]=mx(y[i],y[x[j].X]+(x[j].Y-x[j].X));
if (y[i]>p)
p=y[i];
}
printf("%ld\n",p); */
sort(x+1,x+n+1,cmpf);
for (i=1;i<=n;i++)
{
y[x[i].Y]=y[x[i-1].Y];
if (x[i].X>=x[i-1].Y)
y[x[i].X]=mx(y[x[i].X],y[x[i-1].Y]);
else
if (x[i].X>=x[i-1].X)
y[x[i].X]=mx(y[x[i].X],y[x[i-1].X]);
for (j=i;j>=1;j--)
if (x[j].Y==x[i].Y)
{
y[x[i].Y]=mx(y[x[i].Y],y[x[j].X]+(x[j].Y-x[j].X));
if (x[i].X>=x[j].Y)
y[x[i].X]=mx(y[x[i].X],y[x[j].Y]);
else
if (x[i].X>=x[j].X)
y[x[i].X]=mx(y[x[i].X],y[x[j].X]);
}
if (y[x[i].Y]>p)
p=y[x[i].Y];
if (y[x[i].X]>p)
p=y[x[i].X];
}
printf("%ld\n",p);
return 0;
}