Pagini recente » Cod sursa (job #2258949) | Cod sursa (job #1609842) | Cod sursa (job #1295652) | Cod sursa (job #1488355) | Cod sursa (job #301302)
Cod sursa(job #301302)
#include <algorithm>
#define DIM 1000005
#define LogN 18
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].b,&v[i].a);
}
int cmp (concert a,concert b)
{
return a.a<b.a || (a.a==b.a && a.b<b.b);
}
int cbin (int val)
{
int nr=0,put=LogN;
while (put--)
if (nr+1<<put<=n)
if (v[nr+1<<put].a<=val)
nr+=1<<put;
return nr;
}
int max (int a,int b)
{
if (a>b)
return a;
return b;
}
void solve ()
{
int i,x;
for (i=1; i<=n; ++i)
{
b[i]=b[i-1];
x=cbin (v[i].b);
b[i]=max(b[i],b[x]+v[i].a-v[i].b);
}
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;
}