Pagini recente » Cod sursa (job #2966537) | Cod sursa (job #335804) | Cod sursa (job #690990) | Cod sursa (job #860488) | Cod sursa (job #185058)
Cod sursa(job #185058)
#include <stdio.h>
int a[30000],b[30000],best[30000],n,max,m1,ult[30000];
void qsort(int li,int ls)
{
if (ls-li>0)
{
int i1=0,j1=-1,i=li,j=ls;
while (i<j)
{
if (b[i]>b[j])
{
b[i]^=b[j]^=b[i]^=b[j];
a[i]^=a[j]^=a[i]^=a[j];
int aux=i1;
i1=-j1;
j1=-aux;
}
i+=i1;
j+=j1;
}
qsort(li,i-1);
qsort(i+1,ls);
}
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%d\n",&n);
int i,j;
for (i=0;i<n;i++)
scanf("%d %d\n",&a[i],&b[i]);
qsort(0,n-1);
best[0]=b[0]-a[0];
max=b[0]-a[0];
ult[0]=-1;
for (i=1;i<n;i++)
{
best[i]=b[i]-a[i];
for (j=ult[i-1]+1;j<i;j++)
if (b[j]<=a[i]&&m1<best[j])
{
m1=best[j];
ult[i]=j;
}
best[i]+=m1;
if (max<best[i])
max=best[i];
}
printf("%d\n",max);
return 0;
}