Cod sursa(job #167912)

Utilizator tm_raduToma Radu tm_radu Data 30 martie 2008 13:06:00
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <stdio.h>
#define NM 100001

int n, tmax;
int t[NM];
int i, j, k;
int a[NM], b[NM];

void Qsort(int st, int dr);

int main()
{
    freopen("heavymetal.in", "r", stdin);
    freopen("heavymetal.out", "w", stdout);
    scanf("%d", &n);
    for ( i = 1; i <= n; i++ )
        scanf("%d %d", &a[i], &b[i]);
    Qsort(1, n);
    for ( i = 1; i <= n; i++ )
    {
        t[i] = b[i]-a[i]; 
        for ( j = 1; j <= i-1; j++ )
            if ( b[j] > a[i] ) break;
            else 
                if ( t[i] < t[j] + (b[i]-a[i]) )
                    t[i] = t[j] + b[i]-a[i];
        if ( tmax < t[i] ) tmax = t[i];
    }        
    
    printf("%d\n", tmax);
    
    return 0;
}

void Qsort(int st, int dr)
{
    int i = st-1;
    int j = dr+1;
    do
    {
        do { i++; } while ( b[i] < b[st] || (b[i] == b[st] && a[i] > a[st]) );
        do { j--; } while ( b[st] < b[j] || (b[st] == b[j] && a[st] > a[j]) );
        if ( i <= j )
        {
            int aux = a[i]; a[i] = a[j]; a[j] = aux;
            aux = b[i]; b[i] = b[j]; b[j] = aux;
        }
    } while ( i <= j );
    if ( i < dr ) Qsort(i, dr);
    if ( st < j ) Qsort(st, j);
}