Pagini recente » Cod sursa (job #2578526) | Cod sursa (job #2750801) | Cod sursa (job #553287) | Cod sursa (job #419498) | Cod sursa (job #167269)
Cod sursa(job #167269)
# include <stdio.h>
using namespace std;
# define FIN "heavymetal.in"
# define FOUT "heavymetal.out"
# define MAX_N 100001
typedef struct trio
{
long a,b,s;
};
long n,i;
trio v[MAX_N];
void down(long i, long n)
{
long fiu=i << 1,tata=i;
trio l=v[i];;
while (fiu<=n)
{
if (fiu<n && v[fiu].b<v[fiu+1].b) fiu++;
if (l.b<v[fiu].b)
{
v[tata]=v[fiu];
tata=fiu;
fiu=fiu << 1;
}
else fiu=n+1;
}
v[tata]=l;
}
void heapsort()
{
long i,aux;
trio m;
aux=n >> 1;
for (i = aux; i >= 1; i--)
down(1,n);
for (i = n; i > 1; i--)
{
m=v[i];
v[i]=v[1];
v[1]=m;
down(1,i-1);
}
}
long search(long st, long dr, long vl)
{
long mij,poz=0,max=0;
while (st<=dr)
{
mij=(st+dr)>>1;
if (v[mij].b<=vl)
{
if (v[mij].s>max)
{
max=v[mij].s;
poz=mij;
}
st=mij+1;
}
else dr=mij-1;
}
return poz;
}
void solve()
{
long aux,i;
for (i=1; i<=n; i++)
{
aux=search(1,i-1,v[i].a);
if (v[aux].s+v[i].b-v[i].a>v[i-1].s)
v[i].s=v[aux].s+v[i].b-v[i].a;
else
v[i].s=v[i-1].s;
}
printf("%ld",v[n].s);
}
int main()
{
freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
scanf("%ld",&n);
for (i=1; i<=n; i++)
scanf("%ld %ld",&v[i].a,&v[i].b);
heapsort();
solve();
return 0;
}