Pagini recente » Cod sursa (job #2672443) | Cod sursa (job #1319849) | Cod sursa (job #1569518) | Cod sursa (job #2797784) | Cod sursa (job #2051882)
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fi("heavymetal.in");
ofstream fo("heavymetal.out");
typedef struct time{int x,y,dif;} TIME;
TIME A[100001];
int n,i,j,ind,B[100001];
long long Best[100001];
bool cmp(TIME a, TIME b)
{
return a.y<b.y;
}
int bs(int st, int dr, int val)
{
int mij;
while(st<=dr)
{
mij=(st+dr)/2;
if(B[mij]<val)
st=mij+1;
else
dr=mij-1;
}
return st;
}
void normalizare()
{
sort(B+1,B+2*n+1);
for(i=1; i<=n; i++)
{
A[i].x=bs(1,2*n,A[i].x);
A[i].y=bs(1,2*n,A[i].y);
}
}
int main()
{
fi>>n;
for(i=1; i<=n; i++)
{
fi>>A[i].x>>A[i].y;
A[i].dif=A[i].y-A[i].x;
B[2*i-1]=A[i].x;
B[2*i]=A[i].y;
}
normalizare();
sort(A+1,A+n+1,cmp);
ind=1;
for(i=1; i<=A[n].y; i++)
{
Best[i]=Best[i-1];
while(ind<=n && A[ind].y<=i)
{
if(A[ind].y==i)
Best[i]=max(Best[i],Best[A[ind].x]+A[ind].dif);
ind++;
}
}
fo<<Best[A[n].y]<<"\n";
fi.close();
fo.close();
return 0;
}