Pagini recente » Cod sursa (job #892309) | Cod sursa (job #371549) | Cod sursa (job #2759894) | Cod sursa (job #1396374) | Cod sursa (job #184902)
Cod sursa(job #184902)
#include<stdio.h>
#define max(a,b) ((a>=b)?a:b)
#define N 100001
int n,m,i,j,k,p,b[N],tmax;
struct in{
int a,b;
} a[N],x;
void heap(int i){
int s,d,max;
while((i<<1)<=m){
s=i<<1;d=s+1;max=i;
if(a[max].b<a[s].b||a[max].b==a[s].b&&a[max].a<a[s].a)
max=s;
if(d<=m&&a[max].b<a[d].b||a[max].b==a[d].b&&a[max].a<a[d].a)
max=d;
if(max-i){
x=a[i];
a[i]=a[max];
a[max]=x;
i=max;
}
else
return;
}
}
int main(){
FILE *in=fopen("heavymetal.in","r"),*out=fopen("heavymetal.out","w");
fscanf(in,"%d",&n);
for(i=1;i-n-1;i++)
fscanf(in,"%d%d",&a[i].a,&a[i].b);
m=n;
for(i=n>>1;i;i--)
heap(i);
for(;m-1;){
x=a[1];
a[1]=a[m];
a[m]=x;
m--;
heap(1);
}
j=1;
for(i=1;i-a[n].b-1;i++){
b[i]=b[i-1];
for(;a[j].b==i;j++)
b[i]=max(b[i],b[a[j].a]+a[j].b-a[j].a);
}
fprintf(out,"%d\n",b[a[n].b]);
return 0;
}