Pagini recente » Cod sursa (job #586676) | Cod sursa (job #1952003) | Cod sursa (job #3263189) | Cod sursa (job #1923843) | Cod sursa (job #183617)
Cod sursa(job #183617)
#include<stdio.h>
#include<algorithm>
using namespace std;
struct interval
{int a,b;};
int best[1000000];
interval v[100000];
int compar(const interval &x,const interval &y)
{
if(x.b<y.b)
return true;
if(x.b>y.b)
return false;
if(x.a<y.a)
return true;
return false;
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
int n,i,x,j=0,aux;
scanf("%d",&n);
for(i=0; i<n; i++)
scanf("%d%d",&v[i].a,&v[i].b);
sort(v,v+n,compar);
x=v[n-1].b;
for(i=1; i<=x; i++)
{
best[i]=best[i-1];
while(i==v[j].b)
{
aux=best[v[j].a]+v[j].b-v[j].a;
if(aux>best[i])
best[i]=aux;
j++;
}
}
printf("%d\n",best[x]);
return 0;
}