Pagini recente » Cod sursa (job #786912) | Cod sursa (job #1862145) | Cod sursa (job #422780) | Autentificare | Cod sursa (job #1601049)
#include <iostream>
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
int i,n,j,best[100000],p,u,m,key;
struct formatie{int a,b;}v[100000];
bool compare(formatie x,formatie y)
{
if(x.a==y.a) return x.b<y.b;
return x.a<y.a;
}
int main()
{
f>>n;
for(i=1;i<=n;i++) f>>v[i].a>>v[i].b;
sort(v+1,v+n+1,compare);
for(i=1;i<=n;i++)
{
if(v[i].b-v[i].a>best[i]) best[i]=v[i].b-v[i].a;
if(best[i-1]>best[i]) best[i]=best[i-1];
key=v[i].b;p=i;u=n;
while(p<u)
{
m=(p+u)/2;
if(v[m].a<key) p=m+1;
else u=m;
}
m=(p+u)/2;
if(v[m].a<key) m++;
j=m;
while(j<=n) {
if(best[i]+v[j].b-v[j].a>best[j])
best[j]=best[i]+v[j].b-v[j].a;j++;}
}
g<<best[n];
f.close();
g.close();
return 0;
}