Pagini recente » Cod sursa (job #3130689) | Cod sursa (job #1349633) | Cod sursa (job #86228) | Cod sursa (job #362562) | Cod sursa (job #340300)
Cod sursa(job #340300)
#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;
}