Pagini recente » Cod sursa (job #2620641) | Cod sursa (job #2573157) | Cod sursa (job #133105) | Cod sursa (job #2371301) | Cod sursa (job #1542897)
#include <fstream>
#include <algorithm>
#define maxi 1000000
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int main()
{
int N,a[maxi],b[maxi],best[maxi],i,tmax,sol;
fin>>N;
for(i=1;i<=N;++i)
fin>>a[i]>>b[i];
sort(a+1,a+N+1);
best[1]=b[1]-a[1];
sol=best[1];
for(i=2;i<=N;++i)
{
best[i]=best[i-1];
int s=1;
int d=i-1;
int m=0;
while(s<=d)
{
int mij=(s+d)/2;
if(b[mij]<=a[mij])
{
m=mij;
s=mij+1;
}
else
d=mij-1;
}
best[i]=max(best[i],best[m]+b[i]-a[i]);
sol=max(sol,best[i]);
}
fout<<sol;
return 0;
}