Pagini recente » Cod sursa (job #2015884) | Cod sursa (job #120717) | Profil usureluflorian | Florian Marcu | Cod sursa (job #138545)
Cod sursa(job #138545)
#include<stdio.h>
long int n,i,j,k,a[100002],b[100002],aux,max[100002];
void hd(long int ic,long int nc);
void sh(long int i1,long int i2);
long int cauta(long int st,long int dr);
int main()
{
FILE *f,*g;f=fopen("heavymetal.in","r");g=fopen("heavymetal.out","w");
fscanf(f,"%ld",&n);for(i=1;i<=n;i++)fscanf(f,"%ld%ld",&a[i],&b[i]);
for(i=n/2;i>=1;i--)hd(i,n);
for(i=n;i>=1;i--){sh(1,i);hd(1,i-1);}
max[1]=b[1]-a[1];
for(i=2;i<=n;i++)
{ if(b[i-1]<=a[i])max[i]=max[i-1]+b[i]-a[i];
else
{ max[i]=max[i-1];
if(b[1]<=a[i]) j=cauta(1,i-2);
if(max[j]+b[i]-a[i]>max[i])max[i]=max[j]+b[i]-a[i];
}
}
fprintf(g,"%ld\n",max[n]);
fcloseall();
return 0;
}
void hd(long int ic,long int nc)
{
long int is,is1;
is=2*ic;is1=2*ic+1;
if(is>nc)return;
if(is<nc)if(b[is1]>b[is])is=is1;
if(b[is]>b[ic]){sh(is,ic);hd(is,nc);}
}
void sh(long int i1,long int i2)
{
aux=a[i1];a[i1]=a[i2];a[i2]=aux;
aux=b[i1];b[i1]=b[i2];b[i2]=aux;
}
long int cauta(long int st,long int dr)
{ long int mid;
if(st==dr) return st;
mid=(st+dr)/2;
if(b[mid]>a[i]) return cauta(st,mid-1);
return cauta(mid,dr);
}