Pagini recente » Cod sursa (job #809665) | Cod sursa (job #1270594) | Borderou de evaluare (job #1567600) | Cod sursa (job #3139269) | Cod sursa (job #927997)
Cod sursa(job #927997)
#include<cstdio>
#include<algorithm>
using namespace std;
struct interval
{
int st,dr;
};
interval a,b,v[100010];
int n,i,j,st,dr,rez,c[100010],temp;
bool cmp(const interval &a,const interval &b)
{
return a.st<b.st;
}
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;
}
sort(v+1,v+n+1,cmp);
for(i=1;i<=n;i++)
{
a=v[i];
for(j=i-1;j>=0;j--)
{
b=v[j];
if(b.dr<=a.st)
{
temp=c[j]+a.dr-a.st;
if(temp>c[i])
c[i]=temp;
if(temp>rez)
rez=temp;
}
}
}
printf("%d\n",rez);
return 0;
}