Pagini recente » Cod sursa (job #2083080) | Cod sursa (job #2956821) | Cod sursa (job #839881) | Cod sursa (job #3210818) | Cod sursa (job #360531)
Cod sursa(job #360531)
#include<cstdio>
#include<fstream>
#define N 1<<17
using namespace std;
int n,best[N];
struct tru {int a,b;};
tru t[N];
int cmp(const void *p,const void *q)
{
tru x=*(tru*)p,y=*(tru*)q;
if(x.b<y.b)
return -1;
if(x.b>y.b)
return 1;
return 0;
}
int main()
{
freopen ("bridge.in", "r", stdin);
freopen ("bridge.out", "w", stdout);
int i,j,tmax=0;
scanf ("%d", &n);
for (i=1; i<=n; i++) {scanf ("%d %d", &t[i].a, &t[i].b); if (t[i].b>tmax) tmax=t[i].b;}
qsort (t+1,n,sizeof(t[0]),cmp);
int k=1;
for (i=1; i<=tmax; i++)
{
best[i]=best[i-1];
if (t[k].b==i)
{
best[i]=max(best[i], best[t[k].a] + (t[k].b - t[k].a));
k++;
}
}
printf ("%d", best[tmax]);
return 0;
}