Pagini recente » Cod sursa (job #397703) | Cod sursa (job #2880739) | Cod sursa (job #2689021) | Cod sursa (job #2576936) | Cod sursa (job #340522)
Cod sursa(job #340522)
#include <stdio.h>
long a[100002],b[100002],c[100002],d[100002],i,n,j;
void inter(long x,long m,long y){
long c[100002],d[100002];
for(i=x;i<=y;i++){
c[i]=a[i];
d[i]=b[i];
}
long i1=x;
long i2=m+1;
long k=x-1;
while(i1<=m&&i2<=y)
if(d[i1]<d[i2]){
a[++k]=c[i1++];
b[k]=d[i1-1];
}
else{
a[++k]=c[i2++];
b[k]=d[i2-1];
}
for(i=i1;i<=m;i++){
a[++k]=c[i];
b[k]=d[i];
}
for(i=i2;i<=y;i++){
a[++k]=c[i];
b[k]=d[i];
}
}
void sort(long x,long y){
if(x!=y){
long m=(x+y)/2;
sort(x,m);
sort(m+1,y);
inter(x,m,y);
}
}
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]);
sort(1,n);
c[1]=0;
for(i=2;i<=n;i++)
if(a[i]>=b[i-1]) c[i]=c[i-1]+1;
else c[i]=c[i-1];
d[1]=b[1]-a[1];
for(i=2;i<=n;i++){
j=1;
d[i]=d[i-1];
while(j<=n){
if(c[j]==c[i]-1)
if (d[i]<d[j]+b[i]-a[i])
d[i]=d[j]+b[i]-a[i];
if(c[j]>c[i]-1) break;
j++;
}
}
fprintf(g,"%ld\n",d[n]);
fclose(f);
fclose(g);
return 0;
}