Pagini recente » Cod sursa (job #850305) | Cod sursa (job #700581) | Cod sursa (job #913713) | Cod sursa (job #2358687) | Cod sursa (job #2301391)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct concert
{
int x, y;
}a[100001];
int d[100001];
int n;
bool cmp(concert a, concert b)
{
return (a.y<b.y || (a.y==b.y && a.x<b.x));
}
int main()
{
fin>>n;
for(int i=1; i<=n; ++i) fin>>a[i].x>>a[i].y;
sort(a+1, a+n+1, cmp);
for(int i=1; i<=n; ++i)
{
d[i]=d[i-1];
int st=0, dr=i;
while(st<dr)
{
int m=(st+dr+1)/2;
if(a[m].y>a[i].x) dr=m-1;
else st=m;
}
d[i]=max(d[i], d[st]+a[i].y-a[i].x);
}
fout<<d[n]<<"\n";
return 0;
}