Cod sursa(job #366367)

Utilizator popoiu.georgeGeorge Popoiu popoiu.george Data 21 noiembrie 2009 17:11:37
Problema Orase Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include<fstream>
#include<iostream>
#define inf "orase.in"
#define outf "orase.out"
#define MaxN 50001
#define MINF -0x3f3f3f3f
using namespace std;

fstream f(inf,ios::in),g(outf,ios::out);

int N;
long M;
long D[MaxN],L[MaxN];
long BestMax=MINF;

void Citire()
{
f>>M>>N;
for(int i=1;i<=N;i++)
    {
    f>>D[i]>>L[i];
    }
}

void Sort(int i,int j)
{
long aux;
if(D[i]>D[j])
    {
    aux=D[i];
    D[i]=D[j];
    D[j]=aux;
    aux=L[i];
    L[i]=L[j];
    L[j]=aux;
    }
else if(D[i]==D[j])
    {
    if(L[i]>L[j])
        {
        aux=L[i];
        L[i]=L[j];
        L[j]=aux;
        }
    }
}

void Merge(int p,int q,int m)
{
long v[MaxN],a[MaxN];
int i,j,k=1;
i=p;j=m+1;
while( (i<=m) && (j<=q) )
    {
    if(D[i]<=D[j])
        {
        v[k]=D[i];
        a[k]=L[i];
        k++;
        i++;
        }
    else
        {
        v[k]=D[j];
        a[k]=L[j];
        k++;
        j++;
        }
    }
if(i<=m)
    {
    for(j=i;j<=m;j++)
        {
        v[k]=D[j];
        a[k]=L[j];
        k++;
        }
    }
else
    {
    for(i=j;i<=q;i++)
        {
        v[k]=D[i];
        a[k]=L[i];
        k++;
        }
    }
k=1;
for(i=p;i<=q;i++)
    {
    D[i]=v[k];
    L[i]=a[k];
    k++;
    }
}

void MergeSort(int i,int j)
{
int m;
if((j-i)<=1)Sort(i,j);
else
    {
    m=(i+j)/2;
    MergeSort(i,m);
    MergeSort(m+1,j);
    Merge(i,j,m);
    }
}

long Maxim(long a,long b)
{
if(a>=b)return a;
return b;
}

int main()
{
long max;
Citire();
MergeSort(1,N);
/*for(int i=1;i<=N;i++)
    {
    g<<D[i]<<" "<<L[i]<<endl;
    }*/
for(int i=1;i<=N;i++)
    {
    max=Maxim(L[i-1]+(D[i]-D[i-1])+L[i],BestMax);
    if(max>BestMax)BestMax=max;
    }
g<<BestMax;
f.close();
g.close();
return 0;
}