Pagini recente » Cod sursa (job #2551737) | Cod sursa (job #3164956) | Cod sursa (job #1640055) | Cod sursa (job #1489904) | Cod sursa (job #1366215)
#include<stdio.h>
//ce faci mihnea?
//poate e n log n
long int n,i,j,k,a[100002],b[100002],aux,max[100002];
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;
}
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) ;
}
}
long int cauta(long int st,long int dr)
{
long int mid;
mid=(st+dr)/2;
if(mid==st) return mid;
if(b[mid]<=a[i]) return cauta(mid,dr);
return cauta(st,mid);
}
int main()
{
FILE *fin,*fout;
fin=fopen("heavymetal.in","r");
fout=fopen("heavymetal.out","w");
fscanf(fin,"%ld",&n);
for(i=1;i<=n;i++) fscanf(fin,"%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);
}
for(i=1;i<=n;i++)
{
j=cauta(0,i);
max[i]=(max[i-1]>max[j]+b[i]-a[i])?max[i-1]:max[j]+b[i]-a[i];
}
fprintf(fout,"%ld\n",max[n]);
fclose(fin);
fclose(fout);
return 0;
}