Pagini recente » Cod sursa (job #668536) | Cod sursa (job #2458315) | Cod sursa (job #1551354) | Cod sursa (job #2203054) | Cod sursa (job #2561838)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct kys{int x,y;}a[100001];
int compare (kys a,kys b)
{
return a.x<b.x||a.x==b.x&&a.y<b.y;
}
int n,i,max1,s[100001],j,st,dr,mid;
int main()
{
fin>>n;
for(i=1;i<=n;i++)
{
fin>>a[i].x>>a[i].y;
}
sort(a+1,a+n+1,compare);
for(i=1;i<=n-1;i++)
{
st=i+1;
dr=n;
while(st<dr)
{
mid=(st+dr)/2;
if(a[mid].x>=a[i].y) st=mid+1;
else dr=mid-1;
}
for(j=mid-1;j<=n;j++)
{
if(a[i].y<=a[j].x&&s[j]<s[i]+a[i].y-a[i].x)s[j]=s[i]+a[i].y-a[i].x;
//else break;
}
}
for(i=1;i<=n;i++)
{
s[i]+=(a[i].y-a[i].x);
if(s[i]>max1) max1=s[i];
}
fout<<max1;
return 0;
}