Pagini recente » Cod sursa (job #861954) | Cod sursa (job #2848406) | Cod sursa (job #2746942) | Cod sursa (job #1758591) | Cod sursa (job #1066415)
#include <algorithm>
#include <fstream>
#define PII pair<int, int>
#define x first
#define y second
using namespace std;
const int N=10004;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
PII a[N];
int b[N];
bool comp(PII a, PII b)
{
return a.y<b.y;
}
int bs(int n, int val)
{
int i, step;
for(step=1;step<n;step<<=1);
for(i=0;step;step>>=1)
{
if(i+step<=n&&a[i+step].y<=val) i+=step;
}
return i;
}
int main()
{
int n, i, x;
fin>>n;
for(i=1;i<=n;i++) fin>>a[i].x>>a[i].y;
sort(a+1, a+n+1, comp);
for(i=1;i<=n;i++)
{
x=bs(i, a[i].x);
b[i]=max(b[i-1], b[x]+a[i].y-a[i].x);
}
fout<<b[n];
}