Pagini recente » Cod sursa (job #1573947) | Cod sursa (job #1227719) | Cod sursa (job #1032367) | Cod sursa (job #2074817) | Cod sursa (job #1471526)
#include <iostream>
#include <stdio.h>
#include <algorithm>
#define NMax 100002
using namespace std;
int A[NMax],B[NMax],Best[NMax];
int TMax;
struct Interval
{
int x,y;
}V[NMax];
struct cmp
{
bool operator () (Interval a, Interval b) const
{
return a.y < b.y;
}
};
int main()
{
int N,x,y,sol;
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());
Best[1]=V[1].y-V[1].x;
sol=Best[1];
for(int i=2;i<=N;i++)
{
Best[i]=Best[i-1];
int s=1;
int d=i-1;
int j=0;
while(s<=d)
{
int mij=(s+d)/2;
if(V[mij].y<=V[i].x)
{
j=mij;
s=mij+1;
}
else
d=mij-1;
}
Best[i]=max(Best[i],Best[j]+V[i].y-V[i].x);
sol=max(sol,Best[i]);
}
printf("%d",sol);
}