Pagini recente » Cod sursa (job #667204) | Cod sursa (job #1197270) | Cod sursa (job #212555) | Cod sursa (job #920683) | Cod sursa (job #1857081)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in ("heavymetal.in");
ofstream out ("heavymetal.out");
int n;
struct timpi
{
int inc;
int sf;
int nr;
}v[100005];
bool cmp ( timpi x, timpi y) {
if ( x.sf < y.sf )
return 1;
return 0;
}
int caut( int t, int n ) {
int i = 0;
int pas=1<<20;
while (pas>0)
{ if ( i + pas <= n && v[i + pas].sf <= t )
i += pas;
pas/=2;
}
return i;
}
int main()
{
in>>n;
int i;
for (i=1;i<=n;i++)
in>>v[i].inc>>v[i].sf;
sort (v+1, v+n+1, cmp);
for (i=1;i<=n;i++)
{
int x=caut(v[i].inc,n);
v[i].nr=max(v[i-1].nr, v[x].nr+(v[i].sf-v[i].inc));
}
out<<v[n].nr;
return 0;
}