Pagini recente » Cod sursa (job #1758659) | Cod sursa (job #2985951) | Cod sursa (job #59852) | Cod sursa (job #1270488) | Cod sursa (job #142300)
Cod sursa(job #142300)
#include<stdio.h>
#include<algorithm>
using namespace std;
#define maxn 100010
pair <int, int> nr[maxn];
int best[maxn],timp[maxn],n,x,maxim;
inline int max(int a,int b){
return a>b?a:b;
}
int caut(int i){
int p=0,u=x-1,mij;
while(p!=u){
mij=(p+u)/2;
if(nr[i].second<=timp[mij])
u=mij;
else
p=mij+1;
}
return p;
}
void dinamic(int i){
int poz,interval;
if(timp[x]<nr[i].first){
++x;
best[x]=best[x-1];
}
poz=caut(i);
interval=nr[i].first-nr[i].second;
timp[x]=nr[i].first;
while(timp[poz]>nr[i].second)
--poz;
best[x]=max(best[x],best[poz]+interval);
if(best[x]>maxim)
maxim=best[x];
}
int main(){
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
int i;
scanf("%d",&n);
for(i=0;i<n;++i)
scanf("%d%d",&nr[i].second,&nr[i].first);
sort(nr,nr+n);
for(i=0;i<n;++i)
dinamic(i);
printf("%d\n",maxim);
fclose(stdin);
fclose(stdout);
return 0;
}