Pagini recente » Cod sursa (job #770424) | Cod sursa (job #1937165) | Cod sursa (job #1128764) | Cod sursa (job #281032) | Cod sursa (job #929619)
Cod sursa(job #929619)
#include<cstdio>
#include<algorithm>
using namespace std;
struct interval
{
int st,dr;
};
interval a,b,v[100010];
int bs;
int n,i,j,st,dr,rez,best[100010],temp,tmax;
bool cmp(const interval &a,const interval &b)
{
return a.dr<b.dr;
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d",&st,&dr);
a.st=st;
a.dr=dr;
v[i]=a;
if(dr>tmax)
{
tmax=dr;
}
}
sort(v+1,v+n+1,cmp);
j=1;
for(i=1;i<=tmax;i++)
{
best[i]=best[i-1];
if(v[j].dr==i)
{
if(best[v[j].st]+(v[j].dr-v[j].st)>best[i])
best[i]=best[v[j].st]+(v[j].dr-v[j].st);
j++;
}
}
printf("%d\n",best[tmax]);
return 0;
}