Pagini recente » Cod sursa (job #2141466) | Cod sursa (job #1028104) | Cod sursa (job #1020755) | Cod sursa (job #2979044) | Cod sursa (job #3224290)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct timp
{int st,dr;
}a[100005];
int comp(timp x,timp b)
{return x.dr<b.dr;
}
int n,i,p,u,sol,mij,j;
long long v[100005];
int main()
{f>>n;
for(i=1;i<=n;i++)f>>a[i].st>>a[i].dr;
sort (a+1,a+n+1,comp);
v[1]=a[1].dr-a[1].st;
for(i=2;i<=n;i++)
{p=1;
u=i;
sol=0;
while(p<=u)
{mij=(p+u)/2;
if(a[i].st>=a[mij].dr) p=mij+1,sol=mij;
else u=mij-1;
}
v[i]=max(v[i-1],a[i].dr-a[i].st+v[sol]);
}
g<<v[n];
}