Cod sursa(job #174411)

Utilizator tm_raduToma Radu tm_radu Data 8 aprilie 2008 20:43:07
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <stdio.h>
#define NM 50001

int n, m;
struct edge {
    int x, y;
} e[NM], aux;
int i, j, k, max, imax, dmax;

void Qsort(int st, int dr);

int main()
{
    freopen("orase.in", "r", stdin);
    freopen("orase.out", "w", stdout);
    scanf("%d %d", &m, &n);
    for ( i = 1; i <= n; i++ )
        scanf("%d %d", &e[i].x, &e[i].y);
    Qsort(1, n);
    
    max = e[1].y;
    for ( i = 2; i <= n; i++ )
    {
        if ( dmax < max + e[i].x-e[i-1].x + e[i].y )
            dmax = max + e[i].x-e[i-1].x + e[i].y;
        max = (max + e[i].x - e[i-1].x) < e[i].y ? e[i].y : (max + e[i].x - e[i-1].x);
    }    
        
    printf("%d\n", dmax);
    return 0;
}

void Qsort(int st, int dr)
{
    int i = st-1;
    int j = dr+1;
    do 
    {
        do { i++; } while ( e[i].x < e[st].x || (e[i].x == e[st].x && e[i].y < e[st].y) );
        do { j--; } while ( e[st].x < e[j].x || (e[st].x == e[j].x && e[st].y < e[j].y) );
        if ( i <= j )
            aux = e[i], e[i] = e[j], e[j] = aux;
    } while ( i <= j );
    if ( i < dr ) Qsort(i, dr);
    if ( st < j ) Qsort(st, j);
}