Pagini recente » Cod sursa (job #1975126) | Cod sursa (job #1003177) | Cod sursa (job #3252623) | Cod sursa (job #518471) | Cod sursa (job #2761605)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 100003;
int n;
struct elem{
int x,y;
}v[NMAX];
int dp[NMAX];
bool cmp(elem a,elem b){
if(a.y == b.y)
return a.x < b.x;
return a.y < b.y;
}
int cb(int val,int dr){
int st = 1,last = 1;
while(dr-st>=0){
int mid = (st + dr)>>1;
if(v[mid].y <= val ){
st = mid + 1;
last = mid;
}else{
dr = mid - 1;
}
}
return last;
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d %d",&v[i].x,&v[i].y);
}
sort(v+1,v+n+1,cmp);
for(int i=1;i<=n;i++){
dp[i] = max(dp[i-1], dp[cb(v[i].x,i-1)] + (v[i].y - v[i].x) );
}
printf("%d\n",dp[n] );
return 0;
}