Pagini recente » Cod sursa (job #283321) | Cod sursa (job #1057533) | Cod sursa (job #281276) | Cod sursa (job #1674261) | Cod sursa (job #2153571)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
int i,d[100001],mid,dr,st,p,poz,n,maxi;
struct meme{
int x,y;
}v[100001];
int cmp(meme a,meme b){
if(a.x==b.x)
return a.x<b.x;
return a.y<b.y;
}
int main()
{ f>>n;
for(i=1;i<=n;i++)
f>>v[i].x>>v[i].y;
sort(v+1,v+n+1,cmp);
d[1]=v[1].y-v[1].x;p=v[1].y;
for(i=2;i<=n;i++){
if(v[i].x>=p){
d[i]=d[i-1]+v[i].y-v[i].x;
p=v[i].y;
if(maxi<d[i]){
maxi=d[i];
p=v[i].y;
}
}
else{
st=1;dr=i-1;poz=0;
while(st<=dr){
mid=(st+dr)/2;
if(v[mid].y<=v[i].x){
st=mid+1;
poz=mid;
}
else
dr=mid-1;
}
d[i]=max(d[i-1],d[poz]+v[i].y-v[i].x);
if(maxi<d[i]){
maxi=d[i];
p=v[i].y;
}
}
}
g<<maxi;
return 0;
}