Pagini recente » Cod sursa (job #2151647) | Cod sursa (job #3287652) | Cod sursa (job #291016) | Cod sursa (job #3254222) | Cod sursa (job #535630)
Cod sursa(job #535630)
#include<stdio.h>
#include<algorithm>
#define NMAX 100001
using namespace std;
FILE *f=fopen("heavymetal.in","r");
FILE *g=fopen("heavymetal.out","w");
struct timp{
int a;
int b;
} v[NMAX];
int ind[NMAX],sol[NMAX],N;
int cmp(const int &x,const int &y){
if( v[x].b < v[y].b)
return 1;
else if(v[x].b == v[y].b && v[x].a == v[y].a)
return 1;
return 0;
}
int cautare_binara(int val,int u){
int p=0,sl=0;
while(p<=u){
int m=(p+u)/2;
if( v[ind[m]].b == val)
sl=m,u=m-1;
else if(v[ind[m]].b < val)
{p=m+1; if(sl==0)sl=m;}
else u=m-1;
}
if(sl!=0)
for(int i=sl;i<=N && v[ind[i]].b==val;++i)
if( sol[i] > sol[sl] )
sl=i;
return sl;
}
int main(){
fscanf(f,"%d",&N);
for(int i=1;i<=N;++i){
fscanf(f,"%d%d",&v[i].a,&v[i].b);
ind[i]=i;}
sort(ind+1,ind+N+1,cmp);
sol[1]=v[ind[1]].b-v[ind[1]].a;
for(int i=2;i<=N;++i)
sol[i]=max(sol[i-1],v[ind[i]].b-v[ind[i]].a+sol[cautare_binara(v[ind[i]].a,i-1)]);
fprintf(g,"%d",sol[N]);
return 0;
}