Pagini recente » Cod sursa (job #3282441) | Cod sursa (job #1518719) | Cod sursa (job #744802) | Cod sursa (job #2933455) | Cod sursa (job #1227731)
#include<stdio.h>
#include<algorithm>
#define N 100000
struct elem{int start;int end;} v[N];
bool cmp(elem a, elem b){
if(a.start<b.start)
return true;
if(a.start>b.start)
return false;
if(a.end<a.end)
return true;
else return false;
}
int best[N];
inline int bsearch(int dr){
int st=0,mij=(st+dr)/2,maxp=0,poz=dr+1;
while(st<=dr){
if(v[poz].start<v[mij].end)
dr=mij-1;
else{
if(best[mij]>maxp)
maxp=best[mij];
st=mij+1;
}
mij=(st+dr)/2;
}
return maxp;
}
inline int maxof2(int a,int b){
if(a<b)
return b;
return a;
}
int main(){
FILE *fin,*fout;
fin=fopen("heavymetal.in","r");
fout=fopen("heavymetal.out","w");
int n;
fscanf(fin,"%d",&n);
int i;
for(i=0;i<n;i++){
fscanf(fin,"%d%d",&v[i].start,&v[i].end);
}
std::sort(v,v+n,cmp);
best[0]=v[0].end-v[0].start;
for(i=1;i<n;i++){
int poz=bsearch(i-1);
best[i]=maxof2(best[i-1],v[i].end-v[i].start+poz);
}
fprintf(fout,"%d",best[n-1]);
return 0;
}