Cod sursa(job #961157)

Utilizator primulDarie Sergiu primul Data 11 iunie 2013 18:02:03
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>
using namespace std;
 
long M,N;
long L[50005];
long D[50005];
long A[50005];
 
int cmp(const void *p1,const void *p2)
{
    long a1 = *((long *)(p1));
    long a2 = *((long *)(p2));
    return D[a1] - D[a2];
}
 
int main(void)
{
    fstream fin("orase.in",ios::in);
    fstream fout("orase.out",ios::out);
 
    fin >> M >> N;
    for (long a = 0;a < N;a += 1)
    {
        fin >> D[a] >> L[a];
        A[a] = a;
    }
 
    qsort(A,N,sizeof(long),cmp);
 
    long MaxDist = 0;
    long FarDist = L[A[0]];
    long FarDistPos = D[A[0]];
 
    for (long a = 1;a < N;a += 1)
    {
        long MD = FarDist + (D[A[a]] - FarDistPos) + L[A[a]];
        if (MD > MaxDist)
        {
            MaxDist = MD;
        }
 
        if (L[A[a]] > (FarDist + D[A[a]] - FarDistPos))
        {
            FarDist = L[A[a]];
            FarDistPos = D[A[a]];
        }
    }
 
    fout << MaxDist;
 
    fin.close();
    fout.close();
    return 0;
}