Pagini recente » Cod sursa (job #2316679) | Cod sursa (job #1254946) | Cod sursa (job #2476689) | Cod sursa (job #1218883) | Cod sursa (job #147843)
Cod sursa(job #147843)
#include <stdio.h>
#define Nmax 100100
#define LogN 15
struct interval { int x,y; };
interval a[Nmax];
int n, best[Nmax];
inline int max(int a,int b)
{
if (a>b) return a;
return b;
}
inline int comp(interval a,interval b)
{
if (a.x < b.x) return 1;
if (a.x > b.x) return 0;
if (a.y < b.y) return 1;
return 0;
}
int search(int X)
{
int ret=0,t;
#define q(W) if(ret + (1<<(W)) <= n) if (a[ret + (1<<(W))].x <= X) ret += (1<<(W));
t = LogN;
while(t--) q(t);
return ret;
}
void sort(int st,int dr)
{
int i=st,j=dr;
interval m=a[(st+dr)/2], aux;
do
{
while (comp(a[i],m)) ++i;
while (comp(m,a[j])) --j;
if (i<=j)
{
aux = a[i];
a[i]= a[j];
a[j]= aux;
++i; --j;
}
} while (i<=j);
if (i<dr) sort(i,dr);
if (st<j) sort(st,j);
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%d", &n);
int i,x;
for (i=1;i<=n;++i)
scanf("%d%d", &a[i].y,&a[i].x);
sort(1,n);
for (i=1;i<=n;++i)
{
best[i] = best[i-1];
x = search(a[i].y);
best[i] = max(best[i],best[x]+a[i].x-a[i].y);
}
/*
for (i=1;i<=n;++i)
printf("%d %d\n", a[i].y, a[i].x);
*/
printf("%d\n", best[n]);
return 0;
}