Pagini recente » Cod sursa (job #2917648) | Cod sursa (job #695800) | Cod sursa (job #1624327) | Cod sursa (job #1649773) | Cod sursa (job #1421600)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int hi,lo,mijl,poz,i,sol[100001],n;
struct cub
{
int st;
int dr;
}v[100001];
int cmp(cub o, cub p)
{
return o.dr<p.dr;
}
int main()
{
fin>>n;
for(i=1;i<=n;i++)
fin>>v[i].st>>v[i].dr;
sort(v+1,v+n+1,cmp);
for(i=1;i<=n;i++)
{
sol[i]=sol[i-1];
lo=1;
hi=i-1;
poz=0;
while(lo<=hi)
{
mijl=lo+(hi-lo)/2;
if(v[mijl].dr<=v[i].st)
{
lo=mijl+1;
poz=mijl;
}
else
hi=mijl-1;
}
sol[i]=max(sol[i],sol[poz]+v[i].dr-v[i].st);
}
fout<<sol[n];
return 0;
}