Cod sursa(job #185058)

Utilizator AlxCojocaru Alexandru Alx Data 24 aprilie 2008 18:38:22
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#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;
}