Pagini recente » Cod sursa (job #2797203) | Cod sursa (job #2965443) | Cod sursa (job #2907781) | Cod sursa (job #2601237) | Cod sursa (job #1622230)
#include <iostream>
#include<fstream>
#include<algorithm>
using namespace std;
struct trupa{long long a,b;}v[100005];
bool comp(trupa x,trupa y)
{
if(x.b==y.b) return x.a<y.a;
return x.b<y.b;
}
int i,j,n,m,p,u,key;
long long best[100005],maxim;
int main()
{
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
f>>n;
for(i=1;i<=n;i++) f>>v[i].a>>v[i].b;
sort(v+1,v+n+1,comp);
for(i=1;i<=n;i++)
{
if(v[i].a>v[1].b)
{
p=1;u=i;key=v[i].a;
while(p<u)
{
m=(p+u)/2;
if(v[m].b<=key) p=m+1;
else u=m;
}
if(v[m].b>key) m--;
best[i]=max(best[m]+v[i].b-v[i].a,maxim);
if(best[i]>maxim) maxim=best[i];
}
else best[i]=max(v[i].b-v[i].a,maxim);
}
g<<best[n];
return 0;
}