Pagini recente » Cod sursa (job #2723446) | Cod sursa (job #1255510) | Cod sursa (job #59362) | Cod sursa (job #1143538) | Cod sursa (job #2378779)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
const int N=100002;
const int L=29;
int n,a,b,d[N];
struct obiect
{
int ora_inc;
int ora_sf;
} v[N];
int caut1(int x)
{
int pas=1<<L;
int r=0;
while(pas!=0)
{
if(r+pas<=n && v[r+pas].ora_sf<=x)
r+=pas;
pas/=2;
}
return r;
}
bool cmp(obiect x, obiect y)
{
return x.ora_sf < y.ora_sf;
}
void citire()
{
in>>n;
for(int i=1; i<=n; ++i) in>>v[i].ora_inc>>v[i].ora_sf;
sort(v+1,v+n+1,cmp);
}
int main()
{
citire();
for(int i=1; i<=n; ++i)
{
int a=v[i].ora_sf-v[i].ora_inc+d[caut1(v[i].ora_inc)];
d[i]=max(d[i-1],a);
}
out<<d[n];
return 0;
}