Cod sursa(job #67912)

Utilizator sealTudose Vlad seal Data 25 iunie 2007 21:32:32
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<stdio.h>
#include<stdlib.h>
#define Nm 50001
#define max(a,b) ((a)>(b)?(a):(b))
int D[Nm],L[Nm],n,m,sol;

void read()
{
    int i;

    freopen("orase.in","r",stdin);
    scanf("%d%d",&m,&n);
    for(i=0;i<n;++i)
        scanf("%d%d",D+i,L+i);

}

int cmp(const void *x, const void *y)
{
    return D[*(int*)x]-D[*(int*)y];
}

void solve()
{
    int P[Nm],M[Nm],i;

    for(i=0;i<n;++i)
        P[i]=i;
    qsort(P,n,sizeof(int),cmp);

    M[n-1]=D[P[n-1]]+L[P[n-1]];
    for(i=n-2;i>0;--i)
        M[i]=max(M[i+1],D[P[i]]+L[P[i]]);

    sol=0;
    for(i=0;i<n-1;++i)
        sol=max(sol,M[i+1]-D[P[i]]+L[P[i]]);
}

void write()
{
    freopen("orase.out","w",stdout);
    printf("%d\n",sol);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}