Pagini recente » Cod sursa (job #1315074) | Cod sursa (job #897563) | Cod sursa (job #197271) | Cod sursa (job #3217770) | Cod sursa (job #1857629)
#include<cstdio>
#include<algorithm>
using namespace std;
struct ceva{int st,dr;};
ceva v[100001];
int d[100001];
bool cmp(ceva a,ceva b){
if(a.dr<b.dr)
return true;
else
return false;
}
int main(){
int n,i,maxi,l1,l2,poz,m;
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d%d",&v[i].st,&v[i].dr);
sort(v+1,v+n+1,cmp);
maxi=0;
for(i=1;i<=n;i++){
l1=1;
l2=i;
poz=0;
while(l1<=l2){
m=(l1+l2)/2;
if(v[m].dr<=v[i].st){
poz=m;
l1=m+1;
}else
l2=m-1;
}
d[i]=maxi;
if(d[poz]+v[i].dr-v[i].st>d[i]){
d[i]=d[poz]+v[i].dr-v[i].st;
maxi=d[poz]+v[i].dr-v[i].st;
}
}
printf("%d",maxi);
return 0;
}