Pagini recente » Cod sursa (job #986719) | Cod sursa (job #1165313) | Cod sursa (job #309998) | Cod sursa (job #2831954) | Cod sursa (job #2694263)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct vrajeala
{
int x,y;
}a[100005];
int n,dp[100005],ma;
bool cmp(vrajeala o, vrajeala p)
{
if (o.x==p.x)
return o.y<p.y;
return o.x<p.x;
}
int main()
{
int i,j,st,dr,sol,mij;
fin >> n;
for (i=1; i<=n; i++)
fin >> a[i].x >> a[i].y;
sort(a+1, a+n+1, cmp);
for (i=1; i<=n; i++)
{
st=1;
dr=i-1;
sol=0;
while (st<=dr)
{
mij=(st+dr)/2;
if (a[mij].y<=a[i].x)
{
sol=mij;
st=mij+1;
}
else dr=mij-1;
}
dp[i]=max(dp[i-1],dp[sol]+a[i].y-a[i].x);
}
for (i=1; i<=n; i++)
ma=max(ma,dp[i]);
fout << ma;
return 0;
}