Pagini recente » Cod sursa (job #1706430) | Cod sursa (job #2223262) | Cod sursa (job #2097046) | Cod sursa (job #1288165) | Cod sursa (job #141943)
Cod sursa(job #141943)
#include<stdio.h>
#define nmax 100000
#define max(a,b) ( (a)>(b)? (a):(b) )
int frig1[nmax],frig2[nmax],sol[nmax];
int schimb(int st,int dr)
{
long x=frig2[st];
long y=frig1[st];
while( st < dr ){
while( st < dr && frig2[dr] >= x )--dr;
frig2[st]=frig2[dr];
frig1[st]=frig1[dr];
while( st < dr && frig2[st] <= x )++st;
frig2[dr]=frig2[st];
frig1[dr]=frig1[st];
}
frig2[st]=x;
frig1[st]=y;
return st;}
void slowsort(int st,int dr)
{
if(st<dr)
{
int m=schimb(st,dr);
slowsort(st,m);
slowsort(m+1,dr);
}
}
int main()
{
freopen("heavy.in","r",stdin);
freopen("heavy.out","w",stdout);
int n,i,j,tmax=0,tmin=0;
scanf("%d",&n);
for(i=1; i<=n; ++i){
scanf("%d%d",&frig1[i],&frig2[i]);
if(frig2[i]>tmax)
tmax=frig2[i];
if( !tmin || frig1[i] < tmin )
tmin=frig1[i];
}
slowsort(1,n);
for(i=1; i<=n; ++i)
printf("%d %d\n",frig1[i],frig2[i]);
for(i=tmin,j=1; i<=tmax; ++i){
sol[i]=sol[i-1];
for(j; frig2[j] == i; ++j){
sol[i] = max ( sol[i] , sol[ frig1[j] ] + (frig2[j]-frig1[j]) );
}
}
printf("%d\n",sol[tmax]);
return 0;
}