Pagini recente » Cod sursa (job #553392) | Cod sursa (job #1472632) | Cod sursa (job #2011136) | Cod sursa (job #2752839) | Cod sursa (job #152332)
Cod sursa(job #152332)
#include <stdio.h>
#include <stdlib.h>
struct ceva
{
int a,b;
};
ceva a[100000];
int e[100000];
int b[100000];
int compare(const void *b,const void *c)
{
int *aa=(int*)b;
int *bb=(int*)c;
if (a[*aa].b<a[*bb].b)
return -1;
if (a[*aa].b>a[*bb].b)
return 1;
return 0;
}
int main()
{
FILE *in,*out;
int n,i,j,x,t,max;
in=fopen("heavymetal.in","r");
out=fopen("heavymetal.out","w");
fscanf(in,"%d",&n);
for (i=1;i<=n;i++)
{
fscanf(in,"%d%d",&a[i].a,&a[i].b);
e[i]=i;
}
qsort(e+1,n,sizeof(e[1]),compare);
max=0;
for (i=1;i<=n;i++)
{
b[i]=a[e[i]].b-a[e[i]].a;
j=i-1;
x=1;
while (j>0&&x)
{
if (a[e[j]].b>a[e[i]].a)
t=b[j];
else
t=b[j]+a[e[i]].b-a[e[i]].a;
if(t>b[i])
b[i]=t;
if (a[e[j]].b<=a[e[i]].a)
x=0;
j--;
}
if (b[i]>max)
max=b[i];
}
fprintf(out,"%d\n",max);
fclose(in);
fclose(out);
return 0;
}