Cod sursa(job #960966)

Utilizator XladhenianGrigorita Vlad-Stefan Xladhenian Data 11 iunie 2013 14:05:41
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 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;
}