Pagini recente » Cod sursa (job #2084326) | Cod sursa (job #754652) | Cod sursa (job #2714906) | Cod sursa (job #1493583) | Cod sursa (job #160679)
Cod sursa(job #160679)
#include <stdio.h>
#include <stdlib.h>
struct ceva
{
int a,b;
};
struct ceva2
{
int a,o;
};
ceva a[100000];
ceva2 b[100000];
int m;
int compare(const void *a,const void *b)
{
ceva *aa=(ceva*)a;
ceva *bb=(ceva*)b;
if (aa->b<bb->b)
return -1;
if (aa->b>bb->b)
return 1;
return 0;
}
int cauta(int x)
{
int p=1,u=m,y;
while (p<u)
{
y=(u+p)/2;
if (x<=b[y].o)
u=y;
else
p=y+1;
}
if (b[u].o<=x)
return u;
else
if (b[u-1].o<=x)
return u-1;
else
return 0;
}
int main()
{
FILE *in,*out;
int n,max=0,t,i;
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);
}
qsort(a+1,n,sizeof(a[1]),compare);
m=0;
for (i=1;i<=n;i++)
{
t=cauta(a[i].a);
if (a[i].b!=b[m].o)
m++;
b[m].o=a[i].b;
if (b[t].a+a[i].b-a[i].a>b[m].a)
{
b[m].a=b[t].a+a[i].b-a[i].a;
}
if (max<b[m].a)
max=b[m].a;
}
fprintf(out,"%d\n",max);
fclose(in);
fclose(out);
return 0;
}