Pagini recente » Cod sursa (job #677959) | Cod sursa (job #1141370) | Cod sursa (job #3175826) | Cod sursa (job #2398902) | Cod sursa (job #1754973)
#include <cstdio>
#include <algorithm>
using namespace std;
int n,p[100002],best[100002];
struct interval{
int x,y;
}a[100002];
bool cmp(int x,int y){
if(a[x].y>a[y].y)return 0;
if(a[x].y==a[y].y&&a[x].x>a[y].x)return 0;
return 1;
}
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", &a[i].x,&a[i].y),p[i]=i;
sort(p+1,p+n+1,cmp);
int Max=a[p[n]].y,j=1;
for(int i=1;i<=Max;++i){
best[i]=best[i-1];
while(a[p[j]].y==i){
best[i]=max(best[i],best[a[p[j]].x]+(a[p[j]].y-a[p[j]].x));
++j;
}
}printf("%d", best[Max]);
return 0;
}