Pagini recente » Cod sursa (job #6353) | Cod sursa (job #2684609) | Cod sursa (job #2955225) | Cod sursa (job #2001701) | Cod sursa (job #258055)
Cod sursa(job #258055)
#include<stdio.h>
#define max(a,b) (a>b?a:b)
FILE *fin=fopen("heavymetal.in","r"),
*fout=fopen("heavymetal.out","w");
int N,x[100005],y[100005],B[100005];
void swap(int i,int j){
y[i]^=y[j];y[j]^=y[i];y[i]^=y[j];
x[i]^=x[j];x[j]^=x[i];x[i]^=x[j];
}
int main(){
fscanf(fin,"%d",&N);
for(int i=1;i<=N;i++){
fscanf(fin,"%d %d",&x[i],&y[i]);
int j=i;
while(j/2 && y[j/2]<y[j]){
swap(j,j/2);
j>>=1;
}
}
int Nh=N;
while(Nh>1){
swap(1,Nh);
--Nh;
int i=1,j;
while(1){
j=i*2;
if(j>Nh) break;
if(j+1<=Nh && y[j+1]>y[j]) ++j;
if(y[j]<y[i]) break;
swap(j,i);
i=j;
}
}
for(int i=1;i<=N;i++){
int j;
B[i]=B[i-1];
for(j=i-1;j&&y[j]>x[i];--j);
B[i]=max(B[i],y[i]-x[i]+B[j]);
}
for(int i=1;i<N;i++)
if(B[i+1]-B[i]<0)
while(1);
fprintf(fout,"%d\n",B[N]);
fclose(fin);
fclose(fout);
return 0;
}