Pagini recente » Cod sursa (job #216508) | Cod sursa (job #579603) | Cod sursa (job #747784) | Cod sursa (job #399134) | Cod sursa (job #347498)
Cod sursa(job #347498)
#include <iostream>
#include <algorithm>
using namespace std;
void open(){
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
}
struct pii{
int id,val,bgn;
bool st;
bool operator <(const pii &X)const{
return (id<X.id) || (id==X.id && st<X.st);
}
};
#define MAXN 100001
typedef long long ll;
int n,x1,x2;
ll f[MAXN],ans=0LL,maks=0LL;
pii X[MAXN*2];
int main(){
open();
scanf("%d",&n);
for (int i=0;i<n;i++){
scanf("%d %d",&x1,&x2);
X[2*i].id=x1;
X[2*i].st=1;
X[2*i].bgn=i;
X[2*i].val=x2-x1;
X[2*i+1].id=x2;
X[2*i+1].st=0;
X[2*i+1].val=x2-x1;
X[2*i+1].bgn=i;
}
n*=2;
sort(X,X+n);
for (int i=0;i<n;i++){
if (X[i].st){
f[X[i].bgn]=f[X[i].bgn]+maks+(ll)X[i].val;
}
else {
maks=max(maks,f[X[i].bgn]);
}
//cout<<X[i].st<<' '<<X[i].id<<' '<<X[i].bgn<<' '<<f[X[i].bgn]<<endl;
}
for (int i=0;i<n/2;i++) ans=max(ans,f[i]);
printf("%lld\n",ans);
//system("pause");
return 0;
}