Pagini recente » Cod sursa (job #157379) | Cod sursa (job #358677) | Cod sursa (job #1322004) | Cod sursa (job #1442804) | Cod sursa (job #522238)
Cod sursa(job #522238)
#include<stdio.h>
#include<algorithm>
using namespace std;
int last=1;
struct interval
{
int x,y;
};
interval f[100010];
bool cmp(interval a,interval b)
{
return a.y<b.y;
}
int bs(int val,int dr)
{
int st=1,med,last=0;
while(st<=dr)
{
med=st+((dr-st)>>1);
if(f[med].y<=val)
{
last=med;
st=med+1;
}
else
dr=med-1;
}
return last;
}
int c[100001];
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
int n,i,poz;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&f[i].x);
scanf("%d",&f[i].y);
}
sort(f+1,f+n+1,cmp);
c[0]=0;
c[1]=f[1].y-f[1].x;
for(i=2;i<=n;i++)
{
c[i]=c[i-1];
poz=bs(f[i].x,i-1);
if(c[poz]+f[i].y-f[i].x>c[i])
c[i]=c[poz]+f[i].y-f[i].x;
}
printf("%d",c[n]);
return 0;
}