Pagini recente » Cod sursa (job #2984881) | Cod sursa (job #1780335) | Cod sursa (job #367491) | Cod sursa (job #2017905) | Cod sursa (job #2769517)
#include <bits/stdc++.h>
#define Y first
#define X second.first
#define V second.second
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int i,maxim,n,j,st,dr,mid,D[100010];
pair<int,pair<int,int>> v[100010];
int main(){
fin>>n;
for(i=1;i<=n;i++)
fin>>v[i].X>>v[i].Y,v[i].V=v[i].Y-v[i].X;
sort(v+1,v+n+1);
D[1]=v[1].V;
for(i=2;i<=n;i++){
D[i]=D[i-1];
if(v[i].X>=v[i-1].Y){
D[i]=D[i-1]+v[i].V;
}else{
st=1;
dr=i-2;
while(st<=dr){
mid=(st+dr)/2;
if(v[i].X>=v[mid].Y)
st=mid+1;
else
dr=mid-1;
}
D[i]=max(D[i],D[dr]+v[i].V);
}
}
fout<<D[n];
return 0;
}