Pagini recente » Cod sursa (job #2735258) | Cod sursa (job #1576419) | Cod sursa (job #1877671) | Cod sursa (job #1411577) | Cod sursa (job #2561830)
#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.y<b.y||a.y==b.y&&a.x<b.x;
}
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;j<=n;j++)
{
if(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;
}