Pagini recente » Cod sursa (job #2930709) | Cod sursa (job #2190539) | Cod sursa (job #1788530) | Cod sursa (job #1822704) | Cod sursa (job #292462)
Cod sursa(job #292462)
#include <algorithm>
#define DIM 1000005
using namespace std;
struct concert {int a,b;} v[DIM];
int b[DIM];
int n;
void read ()
{
int i;
scanf ("%d",&n);
for (i=1; i<=n; ++i)
scanf ("%d%d",&v[i].a,&v[i].b);
}
int cmp (concert a,concert b)
{
return a.b<b.b || (a.b==b.b && a.a<b.a);
}
int cbin (int val)
{
int st,dr,mij,nr;
for (st=1, dr=n; st<=dr; )
{
mij=(st+dr)/2;
if (v[mij].a==val)
nr=mij;
if (v[mij].a>=val)
dr=mij-1;
else
st=mij+1;
}
return nr-1;
}
int max (int a,int b)
{
if (a>b)
return a;
return b;
}
void solve ()
{
int i;
for (i=1; i<=n; ++i)
{
b[i]=b[i-1];
b[i]=max(b[i],b[cbin (v[i].a)]+v[i].b-v[i].a);
}
printf("%d\n", b[n]);
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
read ();
sort(v+1,v+n+1,cmp);
solve ();
return 0;
}