Pagini recente » Cod sursa (job #246885) | Cod sursa (job #240116) | Cod sursa (job #1510152) | Cod sursa (job #9953) | Cod sursa (job #3224294)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct bongos
{
int s,f;
}a[100005];
int n,i,st,dr,sum[100005],x;
int comp(bongos a,bongos b)
{
if(a.f==b.f) return a.s<b.s;
return a.f<b.f;
}
int main()
{
f>>n;
for(i=1;i<=n;i++)
{
f>>a[i].s>>a[i].f;
}
sort(a+1,a+n+1,comp);
sum[1]=a[1].f-a[1].s;
for(i=2;i<=n;i++)
{
st=1;
dr=i;
x=0;
while(st<=dr)
{
int mij=(st+dr)/2;
if(a[mij].f<=a[i].s)
{
st=mij+1;
x=mij;
}
else
dr=mij-1;
}
sum[i]=max(sum[i-1],sum[x]+a[i].f-a[i].s);
}
g<<sum[n];
return 0;
}