Pagini recente » Cod sursa (job #2277161) | Cod sursa (job #1296245) | Cod sursa (job #2176570) | Cod sursa (job #322563) | Cod sursa (job #445041)
Cod sursa(job #445041)
#include<stdio.h>
#include<algorithm>
#define Nmax 100010
#define Max(a,b) a>b ? a : b
using namespace std;
int viz[Nmax],best[Nmax],i,j,n,m,N,K;
struct coord {int poz,val;} crd[Nmax<<1];
struct norm {int x,y,val;} v[Nmax];
int cmp (coord a, coord b)
{
return a.val<b.val;
}
int cmp1 (norm a, norm b)
{
return a.y<b.y;
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d %d",&v[i].x,&v[i].y);
v[i].val=v[i].y-v[i].x;
crd[++K].val=v[i].x;
crd[K].poz=i;
crd[++K].val=v[i].y;
crd[K].poz=i;
}
sort(crd+1,crd+K+1,cmp);
for(i=1;i<=K;i++)
if(crd[i].val!=crd[i-1].val)
{
N++;
if( v[crd[i].poz].x==crd[i].val) v[crd[i].poz].x=N;
if( v[crd[i].poz].y==crd[i].val) v[crd[i].poz].y=N;
}
sort(v+1,v+n+1,cmp1);
for(i=1;i<=n;i++)
if(v[i].y!=v[i-1].y) viz[v[i].y]=i;
for(i=1;i<=N;i++)
if(!viz[i]) best[i]=best[i-1];
else
{
for(j=viz[i];v[j].y==i;j++)
best[i]=Max(best[i],best[v[j].x]+v[j].val);
}
printf("%d",best[N]);
return 0;
}