Cod sursa(job #184980)

Utilizator AlxCojocaru Alexandru Alx Data 24 aprilie 2008 17:16:41
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <stdio.h>
int a[30000],b[30000],best[30000],n,max;
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]=1;
    max=b[0]-a[0];
    for (i=1;i<n;i++)
    {
        best[i]=b[i]-a[i];
        j=i-1;
        while (j>=0&&a[i]<b[j])
            j--;
        if (a[i]>=b[j])
            best[i]+=best[j];
        if (max<best[i])
            max=best[i];
    }
    printf("%d\n",max);
    return 0;
}